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

Solution (Python):
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])

Solution (Python):
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

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

Solution (Python):
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)