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:
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) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    t = [1] * (c + 1)
    for j in range(c):
        t[j + 1] = t[j] * a[i] % MOD
    for j in range(c + 1):
        for k in range(j + 1):
            dp[i + 1][j] += t[k] * dp[i][j - k]
        dp[i + 1][j] %= MOD
print(dp[n][c])

Submission status: Wrong Answer

Solution code:
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) 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 + 1):
            dp[i + 1][j] += pow(a[i], k, MOD) * dp[i][j - k]
        dp[i + 1][j] %= MOD
print(dp[n][c])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
MOD = 10**9+7

n, c = map(int, input().split())
A = np.array(tuple(map(int, input().split())))
B = np.array(tuple(map(int, input().split())))
E = np.zeros((n, c+1), dtype=np.int64)
for j in range(c+1):
  cum = np.array(tuple(pow(k, j, MOD) for k in range(401))).cumsum()%MOD
  E[:, j] = cum[B] - cum[A-1]

dp = np.zeros((n+1, c+1), dtype=np.int64)
dp[0, 0] = 1
for i, e in enumerate(E):
  for j in range(c+1):
    dp[i+1][j:] += dp[i][:c+1-j]*e[j]
  dp[i+1] %= MOD
ans = dp[n, c]
print(ans)

Submission status: Wrong Answer

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 _ in range(N)]
dp[0] = [pow(a[0], k, MOD) for k in range(C+1)]
for i in range(N-1):
    dp[i+1][0] = dp[i][0]
    val = a[i+1]
    row = dp[i]
    valtmp = 1
    for j in range(1,C+1):
        valtmp = (valtmp*val+dp[i][j])%MOD
        dp[i+1][j] = valtmp
print(dp[N-1][C])

Submission status: Wrong Answer

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 _ in range(N)]
dp[0] = [pow(a[0], k, MOD) for k in range(C+1)]
for i in range(N-1):
    dp[i+1][0] = dp[i][0]
    val = a[i+1]
    for j in range(1,C+1):
        tmp = 0
        for k in range(j+1):
            tmp = (tmp + dp[i][k]*pow(val, j-k, MOD))%MOD
        dp[i+1][j] = tmp
print(dp[N-1][C])
# print(dp)

Submission status: Wrong Answer

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

ruiseki = [[0] * (402) for _ in range(c+1)]
for i in range(c + 1):
    for j in range(400):
        ruiseki[i][j + 1] = ruiseki[i][j] + pow(j, i, MOD)
        ruiseki[i][j + 1] %= MOD
  
for i in range(n):
    for all_num in range(c + 1):
        for j in range(all_num + 1):
            # i番目の子供に、j個の飴を配る
            dp[i+1][all_num] += (ruiseki[j][b[i]+1] - ruiseki[j][a[i]]) * dp[i][all_num - j]
            dp[i+1][all_num] %= MOD
print(dp[-1][-1])

Submission status: Wrong Answer

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

ruiseki = [[0] * (402) for _ in range(c+1)]
for i in range(c + 1):
    for j in range(400):
        ruiseki[i][j + 1] = ruiseki[i][j] + j**i
  

for i in range(n):
    for all_num in range(c + 1):
        for j in range(all_num + 1):
            # i番目の子供に、j個の飴を配る
            dp[i+1][all_num] += (ruiseki[j][b[i]+1] - ruiseki[j][a[i]]) * dp[i][all_num - j]
            dp[i+1][all_num] %= MOD
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[0]*(C+1) for i in range(N+1)]
dp[-1][0] = 1
S = [[0]*(C+1) for _ in range(N+1)]
for i in range(N):
    power = [1]*(400+1)
    for j in range(C+1):
        for x in range(A[i], B[i]+1):
            S[i][j]+=power[x]
            power[x]*=x
for i in range(N):#iばんめ
    for j in range(C+1):#jこのキャンディー
        for k in range(j+1):#iばんめにk子くばる
            dp[i][j] += dp[i-1][j-k]*S[i][k]
dp[-2][-1]

Submission status: Wrong Answer

Solution code:
def examE(mod):
    N, C = LI()
    A = LI(); B = LI()
    dp = [[0]*(C+1) for _ in range(N+1)]
    dp[0][0] = 1
    if A==B:
        X = A
        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
    ans = dp[N][C]%mod
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(mod)

Submission status: Wrong Answer

Solution code:
def examE(mod):
    N, C = LI()
    A = LI(); B = LI()
    dp = [[0]*(C+1) for _ in range(N+1)]
    dp[0][0] = 1
    if A==B:
        X = A
        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)
    ans = dp[N][C]
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(mod)

Submission status: Wrong Answer

Solution code:
def main():
    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])
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    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])
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    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
    
    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] + pow(j+1,i,mod))%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 + pow(A[i],k,mod)*dp[i-1][j-k])%mod
            dp[i][j] = tmp
    print(dp[N-1][C])
    
    
main()

Submission status: Wrong Answer

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():
    # S[i][c]: X[i]^c (A[i]<=X[i]<=B[i]) の合計
    S = np.zeros((N, C + 1), dtype=int)
    S[:, 0] = B - A + 1
    for i in range(N):
        ex = np.arange(A[i], B[i] + 1, dtype=int)
        s = np.ones_like(ex, dtype=int)
        for c in range(1, C + 1):
            s *= ex
            s %= MOD
            S[i, c] = s.sum()

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

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

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

# 解説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, dtype=int)
B = np.array(B, dtype=int)


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


# 部分点
print(f(A))

Submission status: Wrong Answer

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(n):
    dp[i+1][0] = b[i] - a[i] + 1
for i in range(1, n+1):
    for j in range(1, m+1):
        for k in range(j+1):
            l = a[i - 1]
            r = b[i - 1]
            # print(j-k)
            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: Wrong Answer

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):
    # n個与えた時の得点
    arr = kth_pow_cum[:,b] - kth_pow_cum[:,a-1]
    dp = np.convolve(dp,arr)[:C+1] % MOD

answer = dp[C]
print(answer)

Submission status: Wrong Answer

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

sig = [[0 for _ in range(max(b)+1)] for _ in range(c+1)]
for i in range(c+1):
	for j in range(1, max(b)+1):
		sig[i][j] = sig[i][j-1] + pow(j, i, MOD)
		sig[i][j] %= MOD

def sigma(C, A, B):
	return sig[C][B] - sig[C][A-1]

dp = [[0 for _ in range(c+1)] for _ in range(n)]
for j in range(c+1):
	dp[0][j] = sigma(j, a[0], b[0])

for i in range(1, n):
	for j in range(c+1):
		for k in range(j+1):
			dp[i][j] += dp[i-1][k] * sigma(j-k, a[i], b[i])
			dp[i][j] %= MOD

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

Submission status: Wrong Answer

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
if A!=B:
    print(0)
    sys.exit()
L=[[pow(A[i],j,mod) for i in range(N)] for j in range(C+1)]
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 k in range(C+1):
        for l in range(k+1):
            dp[i][k]+=dp[i-1][l]*L[k-l][i]
            dp[i][k]%=mod
#print(dp)
print(dp[N-1][C])

Submission status: Wrong Answer

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=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
if A!=B:
    print(0)
    sys.exit()
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 k in range(C+1):
        for l in range(k+1):
            dp[i][k]+=dp[i-1][l]*(pow(A[i],k-l,mod))
            dp[i][k]%=mod
#print(dp)
print(dp[N-1][C])

Submission status: Wrong Answer

Solution code:
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
n,k= map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[0]*(k+1) for i in range(n+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
        for j in range(k+1):
                for l in range(j+1):
                        dp[i+1][j] += dp[i][j-l]*(pow(a[i],l,mod))
                dp[i+1][j] %= mod 
print(dp[n][k])

Submission status: Wrong Answer

Solution code:
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
n,k= map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[0]*(k+1) for i in range(n+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
        for j in range(k+1):
                for l in range(j+1):
                        dp[i+1][j] += dp[i][j-l]*(pow(a[i],l,mod))
                dp[i+1][j%mod] 
print(dp[n][k])

Submission status: Wrong Answer

Solution code:
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
n,k= map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[0]*(k+1) for i in range(n+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
        for j in range(k+1):
                for l in range(j+1):
                        dp[i+1][j] += dp[i][j-l]*(pow(a[i],l,mod))
print(dp[n][k])

Submission status: Wrong Answer

Solution code:
N, C =  (int(i) for i in input().split())
A =  [int(i) for i in input().split()]
B =  [int(i) for i in input().split()]

dp = [[0] * (2*C + 1) for i in range(N+1)]
dp[0][0] = 1

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

for i in range(N):
    for j in range(C+1):
        for k in range(C+1): 
            dp[i+1][j+k] += dp[i][j] * power(A[i], k)
            dp[i+1][j+k] = dp[i+1][j+k] % 1000000007

print(dp[N][C])

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
mod = 7 + 10**9

if A == B:
    DP = [[None for c in range(C+1)] for n in range(N+1)]
    for c in range(C+1):
        DP[0][c] = 0
    DP[0][0] = 1
    for n in range(N):
        for c in range(C+1):
            total = 0
            for k in range(c+1):
                total += (DP[n][c-k] * (A[n] ** k)) % mod
                total %= mod
            DP[n+1][c] = total
    print(DP[N][C])
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
mod = 7 + 10**9

if A == B:
    def DP(A, C, memo = {}): #次の子にi個の飴を上げるときの活発度
        if len(A) == 1: return (A[0]**C)%mod
        elif C == 0: return 1
        try:
            return memo[(len(A), C)]
        except KeyError:
            activity = 0
            for i in range(C+1):
                Iactivity = (A[0] ** i) % mod
                activity += (Iactivity * DP(A[1:], C-i, memo)) % mod
                activity %= mod
            memo[(len(A), C)] = activity
            return activity

    memo = {}
    print(DP(A, C, memo))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
mod = 7 + 10**9

if A == B:
    def DP(A, C): #次の子にi個の飴を上げるときの活発度
        if len(A) == 1: return (A[0]**C)%mod
        elif C == 0: return 1
        else:
            activity = 0
            for i in range(C+1):
                Iactivity = (A[0] ** i) % mod
                activity += (Iactivity * DP(A[1:], C-i)) % mod
                activity %= mod
            return activity
    print(DP(A, C))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

mod = 10**9+7

# スペース区切りの整数の入力
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()]

dp = np.zeros((n+1, c+1), dtype=np.int32)
dp[0][0] = 1

# i 変数, j 次数
for i in range(1, n+1):
    for j in range(c+1):
        dp[i][j] = np.sum([dp[i-1][k]*(a[i-1]**(j-k)) for k in range(j+1)]) % mod

print(dp[n][c] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

mod = 10**9+7

# スペース区切りの整数の入力
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()]

dp = np.zeros((n+1, c+1), dtype=np.int64)
dp[0][0] = 1

# i 変数, j 次数
for i in range(1, n+1):
    for j in range(c+1):
        dp[i][j] = np.sum([dp[i-1][k]*(a[i-1]**(j-k)) for k in range(j+1)]) % mod

print(dp[n][c] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

mod = 10**9+7

# スペース区切りの整数の入力
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()]

dp = np.zeros((n+1, c+1), dtype=np.int64)
dp[0][0] = 1

# i 変数, j 次数
for i in range(1, n+1):
    for j in range(c+1):
        dp[i][j] = np.sum([dp[i-1][k]*(a[i-1]**(j-k)) for k in range(j+1)])

print(dp[n][c] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

mod = 10**9+7

# スペース区切りの整数の入力
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()]

dp = np.zeros((n+1, c+1), dtype=np.int64)

# i 変数, j 次元
for i in range(n+1):
    for j in range(c+1):
        if i == 0 and j == 0:
            dp[i][j] = 1
        elif j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = 0
        elif i == 1:
            dp[i][j] = a[i-1]**j
        else:
            dp[i][j] = dp[i-1][j] + a[i-1]*dp[i][j-1]
print(dp[n][c] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

mod = 10**9+7

# スペース区切りの整数の入力
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()]

dp = np.zeros((n+1, c+1), dtype=np.int32)

# i 変数, j 次元
for i in range(n+1):
    for j in range(c+1):
        if i == 0 and j == 0:
            dp[i][j] = 1
        elif j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = 0
        elif i == 1:
            dp[i][j] = a[i-1]**j
        else:
            dp[i][j] = dp[i-1][j] + a[i-1]*dp[i][j-1]
print(dp[n][c] % mod)

Submission status: Wrong Answer

Solution code:
n,c = map(int,raw_input().split())
a = map(int,raw_input().split())
b = map(int,raw_input().split())
m = 10**9 +7
# x = map(lambda x : (x[0] + x[1])*(x[1] - x[0] + 1)/2,zip(a,b))
x = [[0 for i in xrange(c+1)] for j in xrange(n)]
for i in xrange(n):
    # print i,j
    for j in xrange(c+1):
        for k in xrange(a[i],b[i]+1):
            x[i][j] += k**j
dp = [[0 for i in xrange(c+1)] for j in xrange(n+1)]
# print x
# print dp
dp[0][0] = 1
for i in xrange(1,n+1):
    for j in xrange(c+1):
        if j == 0:
            dp[i][j] = x[i-1][0]
            continue
        for k in xrange(j+1):
            # print i,j,k,x[i-1]
            dp[i][j] += dp[i-1][j-k] * x[i-1][k]
            dp[i][j] %= m
print dp[-1][-1]

Submission status: Wrong Answer

Solution code:
def solve():
	p = 10**9+7
	N,C = map(int,raw_input().split())
	A = map(int,raw_input().split())
	B = map(int,raw_input().split())
	dp = [[0 for i in xrange(C+1)] for j in xrange(N+1)]
	dp[0][0] = 1
	for i in xrange(1,N):
		for j in xrange(C+1):
			for k in xrange(j+1):
				dp[i][j] = (dp[i][j] + dp[i-1][k]*pow(A[i-1],j-k,p))%p
	for k in xrange(C+1):
		dp[N][C] = (dp[N][C] + dp[N-1][k]*pow(A[N-1],C-k,p))%p
	print dp[N][C]
solve()

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

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

print f(C,N)

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

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

print f(C,N)