CF1970E2.Trails (Medium)

哈利·波特正在日内瓦湖周围的阿尔卑斯山徒步旅行。在这个区域有 $m$ 个小屋，编号为 $1$ 到 $m$。每个小屋都通过一条或多条小路与湖边的中央集合点相连。每条小路要么是短路，要么是长路。第 $i$ 个小屋通过 $s_i$ 条短路和 $l_i$ 条长路与湖相连。

每天，哈利会从他当前所在的小屋走一条小路到日内瓦湖，然后再从湖边走一条小路到任意一个小屋（包括他出发的小屋）。不过，由于他必须在一天内完成徒步，所选的两条小路中至少有一条必须是短路。

如果哈利从小屋 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^9$。

输出路线组合的总数，对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译