311329: CF1970E3. Trails (Hard)

E3. Trails (Hard)time limit per test2 secondsmemory 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^5$.

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

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^5
1 ≤ n ≤ 10^9

输出数据格式：
可能的小径组合数，模 10^9 + 7。

示例：
输入：
3 2
1 0 1
0 1 1

输出：
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^5 1 ≤ n ≤ 10^9 输出数据格式： 可能的小径组合数，模 10^9 + 7。 示例： 输入： 3 2 1 0 1 0 1 1 输出： 18