CF1970E3 Trails (Hard)

哈利·波特正在日内瓦湖周围的阿尔卑斯山徒步旅行。在这个区域有 $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^5$。 $1 \le n \le 10^9$。

输出哈利可能选择的小路组合总数，对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译