Problem:


Score : 800 points

Problem Statement

12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very sorry for your inconvenience.

There are N children in AtCoder Kindergarten, conveniently numbered 1 through N. Mr. Evi will distribute C indistinguishable candies to the children.

If child i is given a candies, the child's happiness will become x_i^a, where x_i is the child's excitement level. The activity level of the kindergarten is the product of the happiness of all the N children.

For each possible way to distribute C candies to the children by giving zero or more candies to each child, calculate the activity level of the kindergarten. Then, calculate the sum over all possible way to distribute C candies. This sum can be seen as a function of the children's excitement levels x_1,..,x_N, thus we call it f(x_1,..,x_N).

You are given integers A_i,B_i (1≦i≦N). Find  modulo 10^9+7.

Constraints

1≦N≦400

1≦C≦400

1≦A_i≦B_i≦400 (1≦i≦N)

Partial Score

400 points will be awarded for passing the test set satisfying A_i=B_i (1≦i≦N).

Input

The input is given from Standard Input in the following format:

N C
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Output

Print the value of  modulo 10^9+7.

Sample Input 1

2 3
1 1
1 1

Sample Output 1

4

This case is included in the test set for the partial score, since A_i=B_i.
We only have to consider the sum of the activity level of the kindergarten where the excitement level of both child 1 and child 2 are 1 (f(1,1)).

If child 1 is given 0 candy, and child 2 is given 3 candies, the activity level of the kindergarten is 1^0*1^3=1.

If child 1 is given 1 candy, and child 2 is given 2 candies, the activity level of the kindergarten is 1^1*1^2=1.

If child 1 is given 2 candies, and child 2 is given 1 candy, the activity level of the kindergarten is 1^2*1^1=1.

If child 1 is given 3 candies, and child 2 is given 0 candy, the activity level of the kindergarten is 1^3*1^0=1.

Thus, f(1,1)=1+1+1+1=4, and the sum over all f is also 4.

Sample Input 2

1 2
1
3

Sample Output 2

14

Since there is only one child, child 1's happiness itself will be the activity level of the kindergarten. Since the only possible way to distribute 2 candies is to give both candies to child 1, the activity level in this case will become the value of f.

When the excitement level of child 1 is 1, f(1)=1^2=1.

When the excitement level of child 1 is 2, f(2)=2^2=4.

When the excitement level of child 1 is 3, f(3)=3^2=9.

Thus, the answer is 1+4+9=14.

Sample Input 3

2 3
1 1
2 2

Sample Output 3

66

Since it can be seen that f(1,1)=4 , f(1,2)=15 , f(2,1)=15 , f(2,2)=32, the answer is 4+15+15+32=66.

Sample Input 4

4 8
3 1 4 1
3 1 4 1

Sample Output 4

421749

This case is included in the test set for the partial score.

Sample Input 5

3 100
7 6 5
9 9 9

Sample Output 5

139123417



Sample input:
2 3
1 1
1 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

###########

N,C = ii()
A=ii()
B=ii()
@memoize
def f(a,n):
    if n==1:
        return A[0]**a
    sum=0
    for i in range(a+1):
        sum += f(a-i,n-1)*(A[n-1]**i)
    return sum

print f(C,N)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import functools

N,C = map(int,input().split())
As = list(map(int,input().split()))
Bs = list(map(int,input().split()))
MOD = 1000000007

@functools.lru_cache(maxsize = None)
def memo(idx,c):
    if idx == N-1:
        return pow(As[-1],c,MOD)
    # if idx == N-2:
    #     v1 = As[-1]
    #     v2 = As[-2]
    #     tmp = sum(pow(v1,c2,MOD) * pow(v2,c-c2,MOD) for c2 in range(c+1))
    #     return tmp % MOD
    else:
        tmp = sum(pow(As[idx],c2,MOD) * memo(idx+1,c-c2) for c2 in range(c+1))
        return tmp % MOD

# small
print(memo(0,C))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import functools

N,C = map(int,input().split())
As = list(map(int,input().split()))
Bs = list(map(int,input().split()))
MOD = 1000000007

@functools.lru_cache(maxsize = None)
def memo(idx,c):
    if idx == N-2:
        v1 = As[-1]
        v2 = As[-2]
        tmp = sum(pow(v1,c2,MOD) * pow(v2,c-c2,MOD) for c2 in range(c+1))
        return tmp % MOD
    else:
        tmp = sum(c2 * memo(idx+1,c-c2) for c2 in range(c+1))
        return tmp % MOD

# small
print(memo(0,C))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import functools

N,C = map(int,input().split())
As = list(map(int,input().split()))
Bs = list(map(int,input().split()))


@functools.lru_cache(maxsize = None)
def memo(idx,c):
    if idx == N-2:
        v1 = As[-1]
        v2 = As[-2]
        return sum(v1**c2 * v2**(c-c2) for c2 in range(c+1))
    else:
        return sum(c2 * memo(idx+1,c-c2) for c2 in range(c+1))

# small
print(memo(0,C))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9 + 7
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [0] * (C + 1)
dp[0] = 1
for i in range(N):
    X = [0] * (C + 1)
    for j in range(C+1):
        for k in range(A[i], B[i] + 1):
            X[j] = (X[j] + pow(k, j, mod)) % mod
    ndp = [0] * (C + 1)
    for j in range(C+1):
        for k in range(C+1-j):
            ndp[j + k] = (ndp[j + k] + dp[j] * X[k]) % mod
    dp = ndp
print(dp[C])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
mod = 10 ** 9 + 7

N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

memo = []
for p in range(C + 1):
    tmp = [pow(i, p, mod) for i in range(401)]
    memo.append(tuple(accumulate(tmp)))


dp = [[0] * (C + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i, (a, b) in enumerate(zip(A, B)):
    for j in range(C + 1):  # 累計でj個配ったことにする
        for k in range(j + 1):  # i番目の子にk個あげる
            dp[i + 1][j] += dp[i][k] * (memo[j-k][b] - memo[j-k][a-1])
            dp[i + 1][j] %= mod

print(dp[N][C])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
U = 400
U = 10

N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


memo = []
for a, b in zip(A, B):
    tmp = []
    for p in range(C + 1):
        val = 0
        for i in range(a, b + 1):
            val += pow(i, p, mod)
            val %= mod
        tmp.append(val)
    memo.append(tmp)


dp = [[0] * (C + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):  # i番目の子に着目
    for j in range(C + 1):  # 累計でj個配ったことにする
        for k in range(j + 1):  # i番目の子にk個あげる
            dp[i + 1][j] += dp[i][k] * memo[i][j - k]
            dp[i + 1][j] %= mod

print(dp[N][C])

Submission status: Time Limit Exceeded

Solution code:
# キャンディーとN人の子供

mod = 10**9 + 7
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def rev(X):
    return pow(X, mod-2, mod)


pow_sum = [[B[i]-A[i]+1 for j in range(C+1)] for i in range(N)]
pow_table = [[1 for j in range(B[i]+1)] for i in range(N)]
for cnt in range(C):
    for i in range(N):
        pow_sum[i][cnt+1] = 0
        for j in range(A[i], B[i]+1):
            pow_sum[i][cnt+1] += pow(j, cnt+1, mod)
        pow_sum[i][cnt+1] %= mod

ans_dp = [[0 for i in range(C+1)] for j in range(N+1)]
# ans_dp[x][y] = 0<=x<=N,0<=y<=C の場合のdp
ans_dp[0][0] = 1
for n in range(1, N+1):
    # ans_dp[n]の更新
    for c in range(C+1):
        # ans_dp[n][c]の更新
        for k in range(c+1):
            ans_dp[n][c] += ans_dp[n-1][k]*pow_sum[n-1][c-k]
        ans_dp[n][c] %= mod
print(ans_dp[N][C] % mod)

Submission status: Time Limit Exceeded

Solution code:
# キャンディーとN人の子供

mod = 10**9 + 7
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def rev(X):
    return pow(X, mod-2, mod)


pow_sum = [[B[i]-A[i]+1 for j in range(C+1)] for i in range(N)]
pow_table = [[1 for j in range(B[i]+1)] for i in range(N)]
for cnt in range(C):
    for i in range(N):

        for j in range(B[i]+1):
            pow_table[i][j] *= j
            pow_table[i][j] %= mod

        for j in range(N):
            pow_sum[i][cnt+1] = sum(pow_table[i][A[i]:B[i]+1]) % mod

ans_dp = [[0 for i in range(C+1)] for j in range(N+1)]
# ans_dp[x][y] = 0<=x<=N,0<=y<=C の場合のdp
ans_dp[0][0] = 1
for n in range(1, N+1):
    # ans_dp[n]の更新
    for c in range(C+1):
        # ans_dp[n][c]の更新
        for k in range(c+1):
            ans_dp[n][c] += ans_dp[n-1][k]*pow_sum[n-1][c-k]
        ans_dp[n][c] %= mod
print(ans_dp[N][C]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7

def main():
  n, c = map(int, input().split())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  E = [[0]*(c+1) for _ in range(n)]
  for j in range(c+1):
    cumsum = tuple(pow(k, j, MOD) for k in range(401))
    cumsum = tuple(accumulate(cumsum))
    for i, (a, b) in enumerate(zip(A, B)):
      E[i][j] = cumsum[b] - cumsum[a-1]

  dp = [[0]*(c+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i, e in enumerate(E):
    for j, f in enumerate(e):
      for k in range(c+1-j):
        dp[i+1][j+k] += dp[i][k]*f
  ans = dp[n][c]%MOD
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7

def main():
  n, c = map(int, input().split())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  E = [[0]*(c+1) for _ in range(n)]
  for j in range(c+1):
    cumsum = tuple(pow(k, j, MOD) for k in range(401))
    cumsum = tuple(accumulate(cumsum))
    for i, (a, b) in enumerate(zip(A, B)):
      E[i][j] = cumsum[b] - cumsum[a-1]

  dp = [[0]*(c+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i, e in enumerate(E):
    for j, f in enumerate(e):
      for k in range(c+1-j):
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
  ans = dp[n][c]
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7

n, c = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
E = [[0]*(c+1) for _ in range(n)]
for j in range(c+1):
  cumsum = tuple(pow(k, j, MOD) for k in range(401))
  cumsum = tuple(accumulate(cumsum))
  for i, (a, b) in enumerate(zip(A, B)):
    E[i][j] = cumsum[b] - cumsum[a-1]

dp = [[0]*(c+1) for _ in range(n+1)]
dp[0][0] = 1
for i, e in enumerate(E):
  for j, f in enumerate(e):
    for k in range(c+1):
      if j+k <= c:
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
ans = dp[n][c]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = np.zeros(c+1, dtype=np.int64)
    dp[0] = 1
    p = np.array([[pow(j, i, mod) for j in range(401)]
                  for i in range(401)], dtype=np.int64)
    for a, b in zip(A, B):
        q = np.sum(p[:, a:b+1], axis=1) % mod
        dp = np.array([sum(dp[i::-1]*q[:i+1] % mod)
                       for i in range(c+1)], dtype=np.int64) % mod
    print(dp[-1] % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = np.zeros(c+1, dtype=np.int64)
    dp[0] = 1
    p = np.array([[pow(j, i, mod) for j in range(401)]
                  for i in range(401)], dtype=np.int64)
    for a, b in zip(A, B):
        q = np.sum(p[:, a:b+1], axis=1) % mod
        dp = [sum(dp[i::-1]*q[:i+1] % mod) % mod for i in range(c+1)]
    print(dp[-1] % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0
    p = [[pow(j, i, mod) for j in range(401)] for i in range(401)]

    for a, b in zip(A, B):
        q = [sum(p[i][a:b+1]) % mod for i in range(c+1)]
        dp = [sum([dp[i-j]*q[j] for j in range(i+1)]) %
              mod for i in range(c+1)]
    ans += dp[-1]
    print(ans % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0
    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        p = [sum([pow(x, i, mod) for x in range(a, b+1)]) %
             mod for i in range(c+1)]
        for i in range(c+1):
            dp2[i] = sum([dp[i-j]*p[j] for j in range(i+1)]) % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0
    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        p = [0]*(c+1)
        for i in range(c+1):
            temp = 0
            for x in range(a, b+1):
                temp += pow(x, i, mod)
            p[i] = temp % mod
        for i in range(c+1):
            for j in range(i+1):
                temp = 0
                dp2[i] += dp[i-j]*p[j]
            dp2[i] = dp2[i] % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9+7
X = [[0]*(C+1) for _ in range(N)]

for i in range(N):
    for j in range(A[i], B[i]+1):
        v = 1
        
        for k in range(C+1):
            X[i][k] += v
            v *= j
            v %= MOD
            
for i in range(N):
    for j in range(C+1):
        for k in range(j+1):
            dp[i+1][j] += dp[i][j-k]*X[i][k]
            dp[i+1][j] %= MOD

print(dp[N][C])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9+7
X = [[0]*(C+1) for _ in range(N)]

for i in range(N):
    for j in range(C+1):
        for k in range(A[i], B[i]+1):
            X[i][j] += pow(k, j, MOD)
            X[i][j] %= MOD
            
for i in range(N):
    for j in range(C+1):
        for k in range(j+1):
            dp[i+1][j] += dp[i][j-k]*X[i][k]
            dp[i+1][j] %= MOD

print(dp[N][C])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9+7
X = [[0]*(C+1) for _ in range(N)]

for i in range(N):
    for j in range(C+1):
        for k in range(A[i], B[i]+1):
            X[i][j] += pow(k, j, MOD)
            
for i in range(N):
    for j in range(C+1):
        for k in range(j+1):
            dp[i+1][j] += dp[i][j-k]*X[i][k]
            dp[i+1][j] %= MOD

print(dp[N][C])

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (c + 1) for i in range(n + 1)]
dp[0][0] = 1

ru = [[0] * 410 for i in range(410)]
for cnt in range(410):
    for x in range(409):
        ru[cnt][x + 1] += ru[cnt][x] + pow(x, cnt, MOD)
      
for ni in range(n):
    for cnt in range(c + 1):
        for ci in range(cnt, c + 1):
            dp[ni + 1][ci] += (ru[cnt][b[ni] + 1] - ru[cnt][a[ni]]) * dp[ni][ci - cnt] 
            dp[ni + 1][ci] %= MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (c + 1) for i in range(n + 1)]
dp[0][0] = 1

for ni in range(n):
    for cnt in range(c + 1):
        ru = 0
        for x in range(a[ni], b[ni] + 1):
            ru += pow(x, cnt, MOD)
            ru %= MOD
        for ci in range(cnt, c + 1):
            dp[ni + 1][ci] += ru * dp[ni][ci - cnt] 
            dp[ni + 1][ci] %= MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (c + 1) for i in range(n + 1)]
dp[0][0] = 1

for ni in range(n):
    for cnt in range(c + 1):
        ru = 0
        for x in range(a[ni], b[ni] + 1):
            ru += pow(x, cnt, MOD)
            ru %= MOD
        for ci in range(c + 1):
            if ci - cnt < 0:
                continue
            dp[ni + 1][ci] += ru * dp[ni][ci - cnt] 
            dp[ni + 1][ci] %= MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,c = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ab = list(zip(a,b))
dp = [[0 for i in range(c+1)] for j in range(n+1)]
mod = 10**9+7
for i in range(c+1):
  dp[0][i] = 1
for i in range(1,n+1):
  a,b = ab[i-1]
  for j in range(a,b+1):
    for k in range(c+1):
      dp[i][k] = (dp[i][k]+pow(j,k,mod))%mod
ans = [[0 for i in range(c+1)] for j in range(n+1)]
ans[0][0] = 1
for i in range(1,n+1):
  for j in range(c+1):
    for k in range(j+1):
      ans[i][j] += dp[i][k]*ans[i-1][j-k]
    ans[i][j] %= mod
print(ans[n][c])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
mod = int(1e+9) + 7
perpetual = [[0 for i in range(401)] for j in range(401)]
for i in range(401):
  perpetual[i][0] = 1
  for j in range(1, 401):
    perpetual[i][j] = (perpetual[i][j-1] * i) % mod
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Med = [[0 for i in range(C+1)] for i in range(N)]
for k in range(C+1):
  for m in range(N):
    for n in range(A[m], B[m] + 1):
      Med[m][k] += perpetual[n][k]
      Med[m][k] %= mod
D = {0: 1}
for i in range(N):
  T = [[j, D[j]] for j in D]
  for j in range(C+1):
    for k in T:
      if j + k[0] in D:
        if j != 0:
          D[j+k[0]] += k[1] * Med[i][j]
          D[j+k[0]] %= mod
        else:
          D[k[0]] *= Med[i][j]
          D[k[0]] %= mod
      else:
        if j + k[0] <= C:
          if j != 0:
            D[j+k[0]] = k[1] * Med[i][j]
            D[j+k[0]] %= mod
          else:
            D[k[0]] *= Med[i][j]
            D[k[0]] %= mod
print(D[C])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
mod = int(1e+9) + 7
perpetual = [[0 for i in range(401)] for j in range(401)]
for i in range(401):
  perpetual[i][0] = 1
  for j in range(1, 401):
    perpetual[i][j] = (perpetual[i][j-1] * i) % mod
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Med = [[0 for i in range(C+1)] for i in range(N)]
for k in range(C+1):
  for m in range(N):
    for n in range(A[m], B[m] + 1):
      Med[m][k] += perpetual[n][k]
      Med[m][k] %= mod
D = {0: 1}
for i in range(N):
  T = [[j, D[j]] for j in D]
  for j in range(C+1):
    for k in T:
      if j + k[0] in D:
        if j != 0:
          D[j+k[0]] += k[1] * Med[i][j]
          D[j+k[0]] %= mod
        else:
          D[k[0]] *= Med[i][j]
          D[k[0]] %= mod
      else:
        if j + k[0] <= C:
          if j != 0:
            D[j+k[0]] = k[1] * Med[i][j]
            D[j+k[0]] %= mod
          else:
            D[k[0]] *= Med[i][j]
print(D[C])

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(c+1) for i in range(n+1)]
dp[0][0] = 1

# forループを更に一つ潰す必要あり
for i in range(n):
    for x in range(a[i], b[i] + 1):
        for all_num in range(c+1):
            for j in range(all_num + 1):
                # i番目の子供に、j個の飴を配る
                dp[i+1][all_num] += x**j * dp[i][all_num - j]
                dp[i+1][all_num] %= MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

# modを取りながらべき乗する
def power_func(a,n,mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

def main():
    N, C = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    mod = 10**9+7

    dp = [[[] for _ in range(C+1)] for _ in range(N)]
    count = B[0] - A[0] + 1
    for c in range(C+1):
        a, b = A[0], B[0]
        dp[0][c].append(power_func(a, c, mod))
        for k in range(1, b-a+1):
            dp[0][c].append((dp[0][c][k-1] + power_func(a+k, c, mod)) % mod)

    for i in range(1, N):
        a, b = A[i], B[i]
        for k in range(b-a+1):
            dp[i][0].append(count * (k+1) % mod)
        for c in range(1, C+1):
            dp[i][c].append((dp[i-1][c][-1] + a*dp[i][c-1][0]) % mod)
            for k in range(1, b-a+1):
                R = dp[i][c][k-1] + dp[i-1][c][-1] + (a+k)*(dp[i][c-1][k]-dp[i][c-1][k-1])
                if R < 0: R += mod
                dp[i][c].append(R%mod)
        count = (count * (b-a+1)) % mod

    print(dp[N-1][C][-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

# modを取りながらべき乗する
def power_func(a,n,mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
mod = 10**9+7
L = 400

dp = [[[0]*(L+1) for _ in range(C+1)] for _ in range(N)]
count = B[0] - A[0] + 1
for c in range(C+1):
    a, b = A[0], B[0]
    dp[0][c][0] = power_func(a, c, mod)
    for k in range(1, b-a+1):
        dp[0][c][k] = (dp[0][c][k-1] + power_func(a+k, c, mod)) % mod
    dp[0][c][L] = dp[0][c][b-a]

for i in range(1, N):
    a, b = A[i], B[i]
    for k in range(b-a+1):
        dp[i][0][k] = count * (k+1) % mod
    for c in range(1, C+1):
        dp[i][c][0] = (dp[i-1][c][L] + a*dp[i][c-1][0]) % mod
        for k in range(1, b-a+1):
            dp[i][c][k] = dp[i][c][k-1] + dp[i-1][c][L] + (a+k)*(dp[i][c-1][k]-dp[i][c-1][k-1])
            if dp[i][c][k] < 0: dp[i][c][k] += mod
            dp[i][c][k] %= mod
        dp[i][c][L] = dp[i][c][b-a]
    count = (count * (b-a+1)) % mod

print(dp[N-1][C][L])

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
readline = sys.stdin.readline
MOD = 10**9+7

N, C = map(int, readline().split())
A = [0] + list(map(int, readline().split()))
B = [0] + list(map(int, readline().split()))

acsq = [list(accumulate([pow(i, j, MOD) for i in range(max(B)+1)])) for j in range(C+1)]
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    a, b = A[i], B[i]
    for c in range(C+1):
        res = 0
        for j in range(c+1):
            res = (res + (acsq[c-j][b] - acsq[c-j][a-1])*dp[i-1][j]) % MOD
        dp[i][c] = res
print(dp[N][C])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  c[i][0] = b[i] - a[i] + 1
for i in range(N):
  for k in range(a[i], b[i] + 1):
    t = 1
    for j in range(C):
      t *= k
      t %= mod 
      c[i][j + 1] += t
      c[i][j + 1] %= mod
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i][k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i][k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(C + 1):
    for k in range(a[i], b[i] + 1):
      c[i][j] += pow(k, j, mod)
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i][k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i][k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(C + 1):
    for k in range(a[i], b[i] + 1):
      c[i][j] += (k ** j) % mod
      c[i][j] %= mod
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i][k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i][k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(C + 1):
    for k in range(a[i], b[i] + 1):
      c[i][j] += (k ** j) % mod
      c[i][j] %= mod
dp = [[0] * (C + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
  for j in range(C + 1):
    for k in range(j, C + 1):
      dp[i + 1][k] += dp[i][j] * c[i][k - j]
      dp[i + 1][k] %= mod
print(dp[-1][-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(C + 1):
    for k in range(a[i], b[i] + 1):
      c[i][j] += k ** j
dp = [[0] * (C + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
  for j in range(C + 1):
    for k in range(j, C + 1):
      dp[i + 1][k] += dp[i][j] * c[i][k - j]
      dp[i + 1][k] %= mod
print(dp[-1][-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def ModInt(mod):
    class _ModInt:
        def __init__(self, value):
            self.value = value % mod

        def __add__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value + other.value)
            else:
                return _ModInt(self.value + other)

        def __sub__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value - other.value)
            else:
                return _ModInt(self.value - other)

        def __radd__(self, other):
            return self.__add__(other)

        def __mul__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value * other.value)
            else:
                return _ModInt(self.value * other)

        def __truediv__(self, other):
            # TODO: 実装
            raise NotImplementedError()

        def __repr__(self):
            return str(self.value)

    return _ModInt


MI = ModInt(MOD)
# 解説AC
N, C = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))

A = np.array(A)
B = np.array(B)


def test_happy(X, counts):
    ret = 1
    for x, c in zip(X, counts):
        ret *= pow(x, c, MOD)
        ret %= MOD
    return ret


def test_f(C, X):
    N = len(X)
    ret = 0
    for sp in itertools.combinations_with_replacement(range(C + 1), N - 1):
        g = [0] + list(sp) + [C]
        counts = [g2 - g1 for g1, g2 in zip(g, g[1:])]
        ret += test_happy(X, counts)
        ret %= MOD
    return ret


def f_partial(X):
    # 部分点
    # dp[c][i]: 各項の次数が c で、i 番目の子供まで見たときの f(X) の値
    dp = np.zeros((C + 1, N), dtype=int)
    dp[0] = 1
    p = 1
    for c in range(1, C + 1):
        p = p * X[0] % MOD
        dp[c, 0] = p
    for i in range(1, N):
        for c in range(1, C + 1):
            dp[c, i] = (dp[c, i - 1] + dp[c - 1, i] * X[i]) % MOD
    return dp[C, -1]


def solve():
    # P[n][c]: n^c
    P = np.empty((B.max() + 1, C + 1), dtype=object)
    P[:] = MI(1)
    P[0] = MI(0)
    for c in range(1, C + 1):
        P[:, c] = P[:, c - 1] * np.arange(len(P))

    # S[i][C-c]: X[i]^c (A[i]<=X[i]<=B[i]) の合計
    cs = P.cumsum(axis=0)
    S = cs[B] - cs[A - 1]
    S = S[:, ::-1]

    # dp[c]: 各項の次数が c で、i 番目の子供まで見たときの f(X) の値
    dp = S[0, ::-1]
    for i in range(1, N):
        for c in reversed(range(C + 1)):
            dp[c] = np.dot(dp[:c + 1], S[i, C - c:])
    return dp[-1]


# print(f_partial([1, 1]))
# print(f_partial([1, 2]))
# print(f_partial([2, 1]))
# print(f_partial([2, 2]))
print(solve())