当前没有测试数据。

4.决斗问题

题目描述

$Alice$和$Bob$喜欢用打牌的方式来决斗。规则如下：

1. 每个人有$n$副牌。

2. 每个人选择一个牌堆出牌，出牌有先后的顺序，若先手的牌数大于等于后手，则先手这一次获胜，否则后手获胜。

3. 每个人都是随机选择牌堆，每个人的决策与自己的想法、策略无关。

4. $Alice$后手。

由于每个人一次只出一堆牌，所以决斗一共进行$n$轮。

$Alice$发现她赢$x$场就可以增加$x^{k}$点的智商，她想要知道她增加智商的期望。

假设你的答案可以表示为$\frac{P}{Q}$，其中$\gcd(P,Q)=1$，请输出$PQ^{-1}\bmod(10^{9}+7)$。

输入格式

输入文件的第一行包含两个正整数$n$，$k$，分别表示牌堆个数和赢$x$盘增加智商的指数。

接下来两行：第一行$n$个非负整数，表示$Alice$的每副牌堆中牌的个数；第二行$n$个非负整数，表示$Bob$的每副牌堆中牌的个数。

数据保证除第二行和第三行的$n$个非负整数按照从小到大的顺序给出。

输出格式

一行，表示$Alice$期望增加的智商点数。

数据范围与提示

样例

3 1
2 3 4
1 3 5

666666673