311327: CF1970E1. Trails (Easy)
Description
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$.
InputThe 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^2$.
$1 \le n \le 10^3$.
OutputThe number of possible combinations of trails, modulo $10^9 + 7$.
ExampleInput3 2 1 0 1 0 1 1Output
18
Output
哈利·波特在日内瓦湖周围的阿尔卑斯山脉远足。该地区有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^2
1 ≤ n ≤ 10^3
输出数据格式:
可能的路径组合数,模10^9 + 7。题目大意: 哈利·波特在日内瓦湖周围的阿尔卑斯山脉远足。该地区有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^2 1 ≤ n ≤ 10^3 输出数据格式: 可能的路径组合数,模10^9 + 7。