walk.in walk.out

小z在徒步旅行。在这个地区有 $m$ 个小木屋，编号从1到 $m$ 。每个小木屋都有一条或多条小路与湖边的中心集合点相连。每条小径或长或短。小木屋 $i$ 与湖边的 $s_i$ 条短路径和 $l_i$ 条长路径相连。

每天，小z都会从他现在所在的小屋步行到洞庭湖，然后从那里步行到 $m$ 个小屋中的任何一个（包括他开始所在的小屋）。不过，由于他必须在一天内走完，所以两条路中至少有一条是短路。

如果小z从 1 号小木屋出发，走 $n$ 天，他可以走的所有路线，一共会经过多少条路？

请给出答案，取模 $10^9 + 7$ 。

输入

第一行包含整数 $m$ 和 $n$ 。

第二行包含 $m$ 个整数、 $s_1, \dots, s_m$ 个整数，其中 $s_i$ 是小木屋 $i$ 和洞庭湖之间的短路径数量。

第三行也就是最后一行包含 $m$ 个整数， $l_1, \dots, l_m$ ，其中 $l_i$ 是小木屋 $i$ 和洞庭湖之间的长路径的数量。

我们有以下约束条件：

$0 \le s_i, l_i \le 10^3$ .

$1 \le m \le 10^2$ .

$1 \le n \le 10^3$ .

输出

小径的可能组合数，取模 $10^9 + 7$ 。

3 2
1 0 1
0 1 1

18

对于20%的数据，$1 \leq n, m \leq 10$

对于100%的数据，与上文描述一致。