311327: CF1970E1. Trails (Easy)

E1. Trails (Easy)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are $m$ cabins, numbered 1 to $m$. Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin $i$ is connected with $s_i$ short trails and $l_i$ long trails to the lake.

Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the $m$ cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short.

How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for $n$ days?

Give the answer modulo $10^9 + 7$.

Input

The first line contains the integers $m$ and $n$.

The second line contains $m$ integers, $s_1, \dots, s_m$, where $s_i$ is the number of short trails between cabin $i$ and Lake Geneva.

The third and last line contains $m$ integers, $l_1, \dots, l_m$, where $l_i$ is the number of long trails between cabin $i$ and Lake Geneva.

We have the following constraints:

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

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

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

Output

The number of possible combinations of trails, modulo $10^9 + 7$.

ExampleInput

3 2
1 0 1
0 1 1

Output

18

题目大意：
哈利·波特在日内瓦湖周围的阿尔卑斯山脉远足。该地区有m座小屋，编号为1到m。每座小屋都通过一条或多条小径与湖边的中心会合点相连。每条小径要么是短的，要么是长的。小屋i与湖之间有s_i条短途小径和l_i条长途小径相连。

每天，哈利从当前所在的小屋走一条小径到日内瓦湖，然后从那里走一条小径到任何一座m座小屋（包括他开始的那座）。然而，由于他必须在一天内完成远足，至少其中一条小径必须是短的。

如果哈利从1号小屋开始，走n天，有多少种可能的路径组合？

答案对10^9 + 7取模。

输入数据格式：
第一行包含整数m和n。
第二行包含m个整数，s_1, ..., s_m，其中s_i是小屋i与日内瓦湖之间的短途小径数。
第三行也是最后一样，包含m个整数，l_1, ..., l_m，其中l_i是小屋i与日内瓦湖之间的长途小径数。
满足以下约束条件：
0 ≤ s_i, l_i ≤ 10^3
1 ≤ m ≤ 10^2
1 ≤ n ≤ 10^3

输出数据格式：
可能的路径组合数，模10^9 + 7。题目大意： 哈利·波特在日内瓦湖周围的阿尔卑斯山脉远足。该地区有m座小屋，编号为1到m。每座小屋都通过一条或多条小径与湖边的中心会合点相连。每条小径要么是短的，要么是长的。小屋i与湖之间有s_i条短途小径和l_i条长途小径相连。 每天，哈利从当前所在的小屋走一条小径到日内瓦湖，然后从那里走一条小径到任何一座m座小屋（包括他开始的那座）。然而，由于他必须在一天内完成远足，至少其中一条小径必须是短的。 如果哈利从1号小屋开始，走n天，有多少种可能的路径组合？ 答案对10^9 + 7取模。 输入数据格式： 第一行包含整数m和n。 第二行包含m个整数，s_1, ..., s_m，其中s_i是小屋i与日内瓦湖之间的短途小径数。 第三行也是最后一样，包含m个整数，l_1, ..., l_m，其中l_i是小屋i与日内瓦湖之间的长途小径数。 满足以下约束条件： 0 ≤ s_i, l_i ≤ 10^3 1 ≤ m ≤ 10^2 1 ≤ n ≤ 10^3 输出数据格式： 可能的路径组合数，模10^9 + 7。