1970E1. Trails (Easy)

dp,1800, https://codeforces.com/problemset/problem/1970/E1

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.

Input

The first line contains the integers m and n.

The second line contains m integers, $s_{1}$ ,…, $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≤ $s_{i}, l_{i}$ ≤ $10^{3}$ .

1≤m≤ $10^{2}$ .

1≤n≤ $10^{3}$ .

Output

The number of possible combinations of trails, modulo 109+7.

Example

Input

3 2
1 0 1
0 1 1

Output

【马铉钦25化院】本题虽然难度标1800，但是是一道比较简单的dp问题。考虑第n天时如果在第i个盆地，想要走到第j个盆地的方法：令 $b_{i}, c_{i}$ 分别代表第i个盆地与中心的长、短路的数目，a(n,i)代表第n天时走到第i个盆地的总方法数，则容易发现有

a (n + 1, j) = \sum_{i = 1}^{m} a (n, i) (b_{i} b_{j} + b_{i} c_{j} + c_{i} b_{j})

使用这个公式进行动态规划即可，实现时可以使用两个一维数组代替二维数组。算法时间复杂度为 $O (n m^{2})$

二维数组：

python

m,n=map(int,input().split())
lis=list(map(int,input().split()))
lil=list(map(int,input().split()))
dp=[[1]+[0]*(m-1) for i in range(n+1)]
r=1000000007
for i in range(1,n+1):
    for j in range(m):
        c=0
        for t in range(m):
            c+=(dp[i-1][t]*(lis[t]*(lil[j]+lis[j])+lil[t]*lis[j]))%r
        
        dp[i][j]=c%r
    
print(sum(dp[n])%r)

一维数组：

python

from copy import copy
m,n=map(int,input().split())
lis=list(map(int,input().split()))
lil=list(map(int,input().split()))
dp=[1]+[0]*(m-1)
dpnew=[0]*m
litr=[[0]*m for i in range(m)]
r=1000000007
for j in range(m):
    for t in range(m):
        litr[j][t]=lis[t]*(lil[j]+lis[j])+lil[t]*lis[j]
for i in range(1,n+1):
    
    for j in range(m):
        c=0
        for t in range(m):
            c+=(dp[t]*litr[j][t])%r
        
        dpnew[j]=c%r
    dp=copy(dpnew)
    
print(sum(dp)%r)

1970E1. Trails (Easy) ​

1970E1. Trails (Easy)