哈利·波特正在日内瓦湖周围的阿尔卑斯山徒步旅行。该区域有 $$$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