6660: Trails (Easy)

# 

## 题面翻译

你正在日内瓦湖周围的阿尔卑斯山徒步旅行。那里有 $m$ 个小木屋，编号从 $1$ 到 $m$。每个小木屋都有一条或多条小路与湖边的中心集合点相连。$i$ 号小木屋通过 $s_i$ 条**短路**和 $l_i$ 条**长路**与湖相连。

每天，你都会从你现在所在的小屋步行到日内瓦湖，然后从那里步行到 $m$ 个小屋中的任何一个(包括你开始所在的小屋)。不过，由于你必须在一天内走完，所以两条路中至少有一条是短路。

如果你从 $1$ 号小木屋出发，走 $n$ 天，你可以走多少条小路？

由于答案可能很大，输出模上 $10^9+7$ 后的答案。

数据范围：

$0 \le s_i, l_i \le 10^3$ 

$1 \le m \le 10^2$

$1 \le n \le 10^3$

翻译来自 [jianhe](https://www.luogu.com.cn/user/613794)。

## 题目描述

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 $ .

## 输入格式

The 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 $ .

## 输出格式

The number of possible combinations of trails, modulo $ 10^9 + 7 $ .

## 样例 #1

### 样例输入 #1

```
3 2
1 0 1
0 1 1
```

### 样例输出 #1

```
18
```