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: Accepted

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] * (N * (C + 1))
mod = 10 ** 9 + 7
for i in range(N):
  c[i * (C + 1)] = 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 * (C + 1) + j + 1] += t
      c[i * (C + 1) + 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 * (C + 1) + k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i * (C + 1) + k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9) + 7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    pow_table = [[0 for _ in range(401)] for _ in range(401)]
    # pow_table[i][j]: i^j
    for i in range(1, 401):
        pow_table[i][0] = 1
    
    for i in range(1, 401):
        for j in range(1, 401):
            pow_table[i][j] = pow_table[i][j-1] * i % MOD
    for i in range(1, 401):
        for j in range(401):
            pow_table[i][j] += pow_table[i-1][j]
            if pow_table[i][j] >= MOD:
                pow_table[i][j] -= MOD
    
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(c+1):
            for k in range(j+1):
                ab = pow_table[b[i-1]][k] - pow_table[a[i-1]-1][k]
                if ab < 0:
                    ab += MOD
                dp[i][j] += dp[i-1][j-k] * ab % MOD
                if dp[i][j] >= MOD:
                    dp[i][j] -= MOD

    print(dp[n][c])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main(N,C,A,B):
    import sys
    input = sys.stdin.readline
    #N,C = map(int,input().split())
    #A = list(map(int,input().split()))
    #B = list(map(int,input().split()))
    mod = 10**9+7
    powA = [[0]*(401) for i in range(401)]
    for i in range(401):
        for j in range(401):
            powA[i][j] = pow(i,j,mod)
    
    S = [[0]*401 for i in range(C+1)]
    for i in range(C+1):
        S[i][0] = 0
    for i in range(C+1):
        for j in range(1,401):
            S[i][j] = (S[i][j-1] + powA[j][i])%mod
    
    dp = [[0]*(C+1) for i in range(N)]
    for i in range(C+1):
        dp[0][i] = S[i][B[0]] - S[i][A[0]-1]
    for i in range(1,N):
        for j in range(C+1):
            tmp = 0
            for k in range(j+1):
                tmp = (tmp + (S[k][B[i]] - S[k][A[i]-1])*dp[i-1][j-k])%mod
            dp[i][j] = tmp
    print(dp[N-1][C])
    #print(S[1])
    
def main2(N,C,A,B):
    import sys
    input = sys.stdin.readline
    #N,C = map(int,input().split())
    #A = list(map(int,input().split()))
    #B = list(map(int,input().split()))
    mod = 10**9+7
    powA = [[0]*(401) for i in range(401)]
    for i in range(401):
        for j in range(401):
            powA[i][j] = pow(i,j,mod)
    
    S = [[0]*400 for i in range(C+1)]
    for i in range(C+1):
        S[i][0] = 1
    for i in range(C+1):
        for j in range(1,400):
            S[i][j] = (S[i][j-1] + powA[j+1][i])%mod
    
    dp = [[0]*(C+1) for i in range(N)]
    for i in range(C+1):
        dp[0][i] = pow(A[0],i,mod)
    for i in range(1,N):
        for j in range(C+1):
            tmp = 0
            for k in range(j+1):
                tmp = (tmp + powA[A[i]][k]*dp[i-1][j-k])%mod
            dp[i][j] = tmp
    print(dp[N-1][C])
    
import sys
input = sys.stdin.readline
N,C = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

if A==B:
    main2(N,C,A,B)
else:
    main(N,C,A,B)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9)+7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    # 部分点
    # dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    # dp[0][0] = 1
    # for i in range(1, n+1):
    #     for j in range(c+1):
    #         for k in range(j+1):
    #             dp[i][j] += dp[i-1][j-k]*pow(a[i-1], k, MOD)
    #             if dp[i][j] >= MOD:
    #                 dp[i][j] -= MOD
    abc = [[0 for _ in range(401)] for _ in range(401)]
    # abc[i][j]: j**i
    for i in range(401):
        abc[0][i] = 1
    abc[0][0] = 0
    for i in range(1, 401):
        for j in range(1, 401):
            abc[j][i] = abc[j-1][i] * i % MOD
    
    for i in range(1, 401):
        for j in range(401):
            abc[j][i] += abc[j][i-1]
            if abc[j][i] >= MOD:
                abc[j][i] -= MOD
    
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(c+1):
            for k in range(j+1):
                accm = abc[k][b[i-1]] - abc[k][a[i-1]-1]
                if accm < 0:
                    accm += MOD
                dp[i][j] += dp[i-1][j-k] * accm % MOD
                if dp[i][j] >= MOD:
                    dp[i][j] -= MOD
    
    print(dp[n][c])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys

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()))


def solve():
    # P[n][c]: n^c
    P = [[1] * (C + 1) for _ in range(max(B) + 1)]
    P[0] = [MI(0)] * (C + 1)
    for i in range(1, len(P)):
        for c in range(1, C + 1):
            P[i][c] = P[i][c - 1] * i

    # cs[n][c]: 0^c + 1^c + ... + n^c
    cs = [[0] * (C + 1) for _ in range(max(B) + 1)]
    for c in range(C + 1):
        s = 0
        for i in range(len(P)):
            s += P[i][c]
            cs[i][c] = s

    # S[i][c]: X[i]^c (A[i]<=X[i]<=B[i]) の合計
    S = [[0] * (C + 1) for _ in range(N)]
    for i in range(N):
        for c in range(C + 1):
            S[i][c] = cs[B[i]][c] - cs[A[i] - 1][c]

    # dp[c]: 各項の次数が c で、i 番目の子供まで見たときの f(X) の値
    dp = S[0][:]
    for i in range(1, N):
        for c in reversed(range(C + 1)):
            s = 0
            for j in range(c + 1):
                s += dp[c - j] * S[i][j]
            dp[c] = s
    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())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    n,c = LI()
    a = LI()
    b = LI()
    s = [[0]*(c+1) for i in range(n)]
    for i in range(n):
        ai,bi = a[i],b[i]
        for x in range(ai,bi+1):
            e = 1
            for k in range(c+1):
                s[i][k] += e
                if s[i][k] >= mod:
                    s[i][k] %= mod
                e *= x
                if e >= mod:
                    e %= mod
    dp = [[0]*(c+1) for i in range(n)]
    for k in range(c+1):
        dp[0][k] = s[0][k]

    for i in range(1,n):
        for k in range(c+1):
            for j in range(k+1):
                dp[i][k] += dp[i-1][j]*s[i][k-j]
                if dp[i][k] >= mod:
                    dp[i][k] %= mod
    print(dp[-1][c])
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]

cumsum = [[1] * 410 for _ in range(410)]
for order in range(405):
    for i in range(1, 405):
        cumsum[order][i] = pow(i, order, MOD) + cumsum[order][i-1]
        cumsum[order][i] %= MOD

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(0, m+1):
        for k in range(j+1):
            l = a[i - 1]
            r = b[i - 1]
            x = (cumsum[j-k][r] - cumsum[j-k][l-1] + MOD) % MOD
            dp[i][j] += dp[i-1][k] * x 
        dp[i][j] %= MOD

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

Submission status: Accepted

Solution code:
import numpy as np
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
mod = 10**9+7
P = np.empty((404, 404), dtype=np.int64)
P[0, :] = 1
ar = np.arange(404, dtype=np.int64)
for i in range(1, 404):
    P[i] = P[i-1] * ar % mod
# この時点で  # P[i, c] = i**c % mod

P = P.cumsum(axis=1, dtype=np.int64) % mod  # P[i, c] = Σ_{k=0}^i k**c % mod
P = P.T

dp = np.zeros(C+1, dtype=np.int64)
dp[0] = 1
for a, b in zip(A, B):
    dp_new = np.zeros(C+1, dtype=np.int64)
    p = (P[b] - P[a-1]) % mod
    for c in range(C+1):
        dp_new[c] = (dp[:c+1] * p[c::-1] % mod).sum()
    dp = dp_new % mod
print(dp[C])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7

N,C = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

# (i,j) に j^i を入れる
kth_pow = np.ones((1024, 401), dtype=np.int64)
rng = np.arange(401, dtype=np.int64)
for i in range(1,C+1):
    kth_pow[i] = kth_pow[i-1] * rng % MOD
kth_pow_cum = kth_pow.cumsum(axis = 1) % MOD
kth_pow_cum[C+1:] = 0

def convolve(A,B,n=32):
    if n == 8:
        return np.rint(np.fft.irfft(np.fft.rfft(A) * np.fft.rfft(B))).astype(np.int64)
    n //= 2
    M = 1 << n
    A1 = A // M
    A2 = A - M * A1
    B1 = A // M
    B2 = B - M * B1
    X = convolve(A1,B1,n)
    Y = convolve(A1-A2,B1-B2,n)
    Z = convolve(A2,B2,n)
    return (X * (M * M % MOD) + (X + Z - Y) * M + Z) % MOD

dp = np.zeros(1024, dtype=np.int64) # これまで配った個数、合計点
dp[0] = 1
for a,b in zip(A,B):
    arr = kth_pow_cum[:,b] - kth_pow_cum[:,a-1]
    dp = convolve(dp,arr)
    dp[C+1:] = 0

answer = dp[C]
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7

N,C = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

# (i,j) に j^i を入れる
kth_pow = np.ones((C+1, 401), dtype=np.int64)
rng = np.arange(401, dtype=np.int64)
for i in range(1,C+1):
    kth_pow[i] = kth_pow[i-1] * rng % MOD
kth_pow_cum = kth_pow.cumsum(axis = 1) % MOD

dp = np.zeros((C+1), dtype=np.int64) # これまで配った個数、合計点
dp[0] = 1
for a,b in zip(A,B):
    arr = kth_pow_cum[:,b] - kth_pow_cum[:,a-1]
    prev = dp
    dp = np.zeros(C+1, dtype=np.int64)
    for n in range(C+1):
        dp[n:] += arr[n] * prev[:C+1-n] % MOD
    dp %= MOD

answer = dp[C]
print(answer)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
mod = 10**9 + 7
X = [list(accumulate([pow(x, d, mod) for x in range(401)])) for d in range(C+1)]
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for d in range(C+1):
        dp[i][d] = sum([dp[i-1][d-k]*(X[k][B[i-1]] - X[k][A[i-1]-1]) for k in range(d+1)])%mod
        
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
N,C=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
mod=10**9+7
table=[[ pow(j,i,mod) for j in range(405)] for i in range(405)]
ntable=[[0]*405 for i in range(405)]
for i in range(405):
    t=0
    for j in range(1,405):
        t+=table[i][j]
        t%=mod
        ntable[i][j]=t
dp=[[0]*(C+1) for i in range(N)]
for i in range(C+1):
    dp[0][i]=((ntable[i][B[0]]-ntable[i][A[0]-1]))%mod
for i in range(1,N):
    for k in range(C+1):
        for l in range(k+1):
            dp[i][k]+=dp[i-1][l]*(ntable[k-l][B[i]]-ntable[k-l][A[i]-1])
            dp[i][k]%=mod
print(dp[N-1][C])

Submission status: Accepted

Solution code:
import sys
N,C=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
mod=10**9+7
table=[[ pow(j,i,mod) for j in range(405)] for i in range(405)]
ntable=[[0]*405 for i in range(405)]
for i in range(405):
    t=0
    for j in range(1,405):
        t+=table[i][j]
        t%=mod
        ntable[i][j]=t
F=[B[i]-A[i]+1 for i in range(N)]
G=[0]*N
t=1
for i in range(N):
    t*=F[i]
    t%=mod
for i in range(N):
    G[i]=(t*pow(F[i],mod-2,mod))%mod
#print(G)
dp=[[0]*(C+1) for i in range(N)]
for i in range(C+1):
    dp[0][i]=((ntable[i][B[0]]-ntable[i][A[0]-1]))%mod#*G[0]
for i in range(1,N):
    for k in range(C+1):
        for l in range(k+1):
            dp[i][k]+=dp[i-1][l]*(ntable[k-l][B[i]]-ntable[k-l][A[i]-1])#*G[i]
            dp[i][k]%=mod
#print(dp)
print(dp[N-1][C])

Submission status: Accepted

Solution code:
n, c = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())

MOD = 10**9+7

memo = [[0]*401 for i in xrange(401)]
for i in xrange(401):
    temp = 0
    for j in xrange(401):
        temp = (temp + pow(j, i, MOD)) % MOD
        memo[j][i] = temp
S = [memo[A[i]-1] for i in xrange(n)]
T = [memo[B[i]] for i in xrange(n)]

dp = [[-1]*(c+1) for i in xrange(n)]
def dfs(i, r):
    if i==-1:
        return r==0
    if dp[i][r] != -1:
        return dp[i][r]
    res = 0
    s = S[i]; t = T[i]
    for j in xrange(0, r+1):
        res = (res + (t[j]-s[j])*dfs(i-1, r-j)) % MOD
    dp[i][r] = res
    return res
print dfs(n-1, c)

Submission status: Runtime Error

Solution code:
for _ in range(test_case):
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: Runtime Error

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

acc = [[0] for _ in range(401)]
for i in range(401):
    for j in range(1, C+2):
        acc[i].append(((acc[i][-1] + pow(j, i, mod)) % mod))

dp = [[0 for _ in range(C+1)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for candy_cur in range(C+1):
        for candy_plus in range(C - candy_cur+1):
            dp[i+1][candy_cur + candy_plus] = (dp[i+1][candy_cur + candy_plus] + (dp[i][candy_cur]\
                                               * ((acc[candy_plus][B[i]] - acc[candy_plus][A[i]-1])%mod)%mod)) % mod

print(dp[-1][C])

Submission status: Runtime Error

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

acc = [[0] for _ in range(401)]
for i in range(401):
    for j in range(1, C+2):
        acc[i].append(acc[i][-1] + j ** i)

dp = [[0 for _ in range(C+1)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for candy_cur in range(C+1):
        for candy_plus in range(C - candy_cur+1):
            dp[i+1][candy_cur + candy_plus] = (dp[i+1][candy_cur + candy_plus] + dp[i][candy_cur]\
                                               * (acc[candy_plus][B[i]] - acc[candy_plus][A[i]-1])) % mod

print(dp[-1][C])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9) + 7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    assert(a==b)
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    pow_table = [[1 for _ in range(401)] for _ in range(n)]
    for i in range(1, 401):
        for j in range(n):
            pow_table[j][i] = pow_table[j][i-1]*a[j]%MOD
    
    for i in range(1, n+1):
        for j in range(1, c+1):
            for k in range(j+1):
                dp[i][j] += dp[i-1][j-k] * pow_table[i-1][k] % MOD
                if dp[i][j] >= MOD:
                    dp[i][j] -= MOD
    print(dp[n][c])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9) + 7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    assert(a==b)
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    pow_table = [[1 for _ in range(401)] for _ in range(n)]
    for i in range(1, 401):
        for j in range(n):
            pow_table[j][i] = pow_table[j][i-1]*a[j]%MOD
    
    for i in range(1, n+1):
        for j in range(1, c+1):
            for k in range(j+1):
                dp[i][j] += (dp[i-1][j-k] * pow_table[i-1][k] % MOD) % MOD
    print(dp[n][c])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9) + 7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    assert(a==b)
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    
    for i in range(1, n+1):
        for j in range(1, c+1):
            for k in range(j+1):
                dp[i][j] += (dp[i-1][j-k] * pow(a[i-1], k, MOD)) % MOD
    print(dp[n][c])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
package main

import (
  "fmt"
  "math"
)

func max(M *[]int) (ret int) {
  ret = (*M)[0]
  for _, m := range (*M) {
    if ret < m {
      ret = m
    }
  }
  return
}

func main() {
  var N, C int
  fmt.Scan(&N, &C)
  A := make([]int, N)
  B := make([]int, N)
  p := int64(math.Pow(10, 9) + 7)
  var x int
  for i := 0; i < N; i++ {
    fmt.Scan(&x)
    A[i] = x
  }
  for i := 0; i < N; i++ {
    fmt.Scan(&x)
    B[i] = x
  }
  B_max := max(&B)
  X := make([][]int64, C + 2)
  for i := 0; i < C + 2; i++ {
    X[i] = make([]int64, B_max + 1)
  }
  for j := 1; j < B_max + 1; j++ {
    X[0][j] = 1
  }
  for i := 0; i < C + 1; i++ {
    for j := 1; j < B_max + 1; j++ {
      X[i + 1][j] = (X[i][j] * int64(j)) % p
      X[i][j] += X[i][j - 1]
    }
  }
  DP := make([][]int64, N + 1)
  for i := 0; i < N + 1; i++ {
    DP[i] = make([]int64, C + 1)
  }
  DP[0][0] = 1
  for i := 1; i < N + 1; i++ {
    for j := 0; j < C + 1; j++ {
      for k := 0; k < j + 1; k++ {
        DP[i][j] += (DP[i - 1][j - k] * (X[k][B[i - 1]] - X[k][A[i - 1] - 1])) % p
      }
      DP[i][j] %= p
    }
  }
  fmt.Println(DP[N][C])
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7

N,C = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

# (i,j) に j^i を入れる
kth_pow = np.ones((1024, 401), dtype=np.int64)
rng = np.arange(401, dtype=np.int64)
for i in range(1,C+1):
    kth_pow[i] = kth_pow[i-1] * rng % MOD
kth_pow_cum = kth_pow.cumsum(axis = 1) % MOD
kth_pow_cum[C+1:] = 0

def convolve(A,B,n=32):
    if n == 8:
        return np.rint(np.fft.irfft(np.fft.rfft(A) * np.fft.rfft(B))).astype(np.int64)
    n //= 2
    M = 1 << n
    A1,A2 = np.divmod(A,M)
    B1,B2 = np.divmod(B,M)
    X = convolve(A1,B1,n)
    Y = convolve(A1-A2,B1-B2,n)
    Z = convolve(A2,B2,n)
    return (X * (M * M % MOD) + (X + Z - Y) * M + Z) % MOD

dp = np.zeros(1024, dtype=np.int64) # これまで配った個数、合計点
dp[0] = 1
for a,b in zip(A,B):
    arr = kth_pow_cum[:,b] - kth_pow_cum[:,a-1]
    dp = convolve(dp,arr)
    dp[C+1:] = 0

answer = dp[C]
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
import itertools

# スペース区切りの整数の入力
n, c = [int(i) for i in sys.stdin.readline().split()]
a = [int(i) for i in sys.stdin.readline().split()]
b = [int(i) for i in sys.stdin.readline().split()]

memo = {}

def f_i(x, c):
    global memo

    if len(x) == 1:
        return x[0]**c

    if str((x, c)) not in memo:
        memo[str((x, c))] = sum([ (x[0]**i) * f_i(x[1:], c-i) for i in xrange(c + 1)])
    
    return memo[str((x, c))]
    
def f(x, c):
    return f_i(x, c)

ranges = [ [ i for i in xrange(a_i, b_i + 1)] for a_i, b_i in zip(a, b)]
print(sum([f(x, c) for x in itertools.product(*ranges)]) % (1000000000+7))