← 返回题目列表

Codeforces · 1970/E3

E3. 小径(困难)

中文机器翻译题面 查看原题

哈利·波特正在日内瓦湖周围的阿尔卑斯山徒步旅行。该区域有 $$$m$$$ 间小屋,编号为 1 至 $$$m$$$。每间小屋都通过一条或多条小径连接到湖边的中央集合点。每条路线或短或长。小屋 $$$i$$$ 通过 $$$s_i$$$ 短径和 $$$l_i$$$ 长径连接至湖泊。

每天,哈利都会从他目前所在的小屋步行到日内瓦湖,然后从那里步行到任意 $$$m$$$ 小屋(包括他开始时所在的小屋)。然而,由于他必须在一天内完成徒步旅行,因此两条路线中至少有一条必须较短。

如果哈利从 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$$$ 为模。

示例

输入 #1

3 2
1 0 1
0 1 1

输出 #1

18