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-----
2 3
1 1
1 1

-----Sample Output-----
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.

Difficulty: competition

Starter code:

Solutions:
MOD=10**9+7
N,C=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
P=[[1] for _ in range(401)]
for _ in range(1,401):
    for i in range(1,401):
        P[i].append(P[i][-1]*i%MOD)
R=[[] for _ in range(N)]
for i,AB in enumerate(zip(A, B)):
    AA,BB=AB
    for a in range(401):
        tmp=0
        for x in range(AA,BB+1):
            tmp+=P[x][a]
            tmp%=MOD
        R[i].append(tmp)
dp=[[0]*(C+1) for _ in range(N+1)]
dp[0][0]=1
for n in range(1,N+1):
    for k in range(C+1):
        for l in range(k+1):
            dp[n][k]+=dp[n-1][k-l]*R[n-1][l]
            dp[n][k]%=MOD
print(dp[N][C])

n,c = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ab = list(zip(a,b))
table = [[0 for i in range(c+1)] for j in range(401)]
mod = 10**9+7
for j in range(c+1):
  if j == 0:
    for i in range(401):
      table[i][j] = 1
  else:
    for i in range(401):
      table[i][j] = table[i][j-1]*i%mod
dp = [[0 for i in range(c+1)] for j in range(n+1)]
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]+table[j][k])%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] = (ans[i][j]+dp[i][k]*ans[i-1][j-k])%mod
print(ans[n][c])

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, f in enumerate(e):
    dp[i+1, j:] += dp[i, :c+1-j]*f
    dp[i+1] %= MOD
ans = dp[n, c]
print(ans)

'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n,c = list(map(int,ipt().split()))
    a = [int(i) for i in ipt().split()]
    b = [int(i) for i in ipt().split()]
    nj = [[] for j in range(c+1)]
    nj[0] = [1]*401
    for j in range(1,c+1):
        for i in range(401):
            nj[j].append(nj[j-1][i]*i%mod)
    snj = [[0] for j in range(c+1)] #累積和,snj[j][b]-snj[j][a-1]で使用
    for j in range(c+1):
        sj = snj[j]
        ssj = nj[j]
        for i in range(1,401):
            sj.append((sj[-1]+ssj[i])%mod)
    dp = [snj[k][b[0]]-snj[k][a[0]-1] for k in range(c+1)]
    for i in range(1,n):
#        print(dp)
        ai = a[i]
        bi = b[i]
        for j in range(c,-1,-1):
            dp[j] = dp[j]*(bi-ai+1)%mod
            for k in range(1,j+1):
                dp[j] = (dp[j]+dp[j-k]*(snj[k][bi]-snj[k][ai-1]))%mod

    print((dp[c]%mod))


    return None

def __starting_point():
    main()

__starting_point()

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)

import sys
N,C=list(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]))



MOD=10**9+7
# 0 to q no i乗和
tab=[]
for i in range(401):
    now=[]
    cnt=0
    for q in range(401):
        cnt+=pow(q,i,MOD)
        now.append(cnt)
    tab.append(now[:])
    
n,c=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

enji=[]
for i in range(n):
    now=[]
    for q in range(c+1):
        now.append(tab[q][B[i]]-tab[q][A[i]-1])
    enji.append(now[:])

dp=[0 for i in range(c+1)]
dp[0]=1
ndp=[0 for i in range(c+1)]
for i in range(n):
    for step in range(c+1):
        val=enji[i][step]%MOD
        for fr in range(c+1-step):
            ndp[fr+step]+=dp[fr]*val%MOD
            ndp[fr+step]%=MOD
            #print(ndp)
    dp=ndp[:]
    ndp=[0 for i in range(c+1)]
    #print(dp)
print(dp[-1])

import sys
N,C=list(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]))



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

MOD = 10**9 + 7

def gen_poly(a, b, c):
  poly = [0 for _ in range(c+1)]
  for x in range(a, b+1):
    xpow = 1
    for i in range(c+1):
      poly[i] += xpow
      xpow = (xpow * x) % MOD
  for i in range(c+1):
    poly[i] %= MOD
  return poly

def mult_polys(p1, p2, dmax):
  ans = [0 for _ in range(dmax+1)]
  for i, c in enumerate(p1):
    for i2, c2 in enumerate(p2):
      if i + i2 <= dmax:
        ans[i+i2] += c*c2
      else:
        break
  ans = [x % MOD for x in ans]
  return ans

polys = [gen_poly(a, b, C) for a, b in zip(A, B)]
prodpoly = [1]
for poly in polys:
  prodpoly = mult_polys(prodpoly, poly, C)

print(prodpoly[C])

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

Sm = [[1 for _ in range(MB+1)]]
for c in range(1,C+1):
  Sm.append([])
  s = Sm[-1]
  sp = Sm[-2]
  for i in range(MB+1):
    s.append((i*sp[i]) % MOD)
    
for c in range(C+1):
  s = Sm[c]
  for i in range(1,MB+1):
    s[i] += s[i-1]
    s[i] %= MOD
    
DP = [[0 for _ in range(C+1)] for _ in range(N+1)]
DP[0][0] = 1
for n in range(1,N+1):
  dp = DP[n]
  dpp = DP[n-1]
  for c in range(C+1):
    for cc in range(C+1-c):
      dp[c+cc] += dpp[c] * (Sm[cc][B[n-1]] - Sm[cc][A[n-1]-1])
      dp[c+cc] %= MOD
print((DP[N][C] % MOD))
    


#!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
def __starting_point():
    C()

__starting_point()

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
    L = 400

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

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

    print(dp[C][L])


def __starting_point():
    main()
__starting_point()

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(i%MOD for i in 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)

n,c = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
mod = 10**9+7

ex400 = [[1] * 401 for _ in range(401)]
for i in range(2,401):
    for j in range(1,401):
        ex400[i][j] = (ex400[i][j-1] * i) % mod

cumsum400 = [[1] * 401 for _ in range(401)]
for i in range(1,401):
    for j in range(401):
        cumsum400[i][j] = (cumsum400[i-1][j] + ex400[i][j]) % mod

dp = [[0] * (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] * (cumsum400[b[i-1]][k] - cumsum400[a[i-1]-1][k])
            dp[i][j] %= mod

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

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

N, C = list(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, 401):
        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]))


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, f in enumerate(e):
    dp[i+1][j:] += dp[i][:c+1-j]*f
    dp[i+1] %= MOD
ans = dp[n, c]
print(ans)

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,c = list(map(int,readline().split()))
*a, = list(map(int,readline().split()))
*b, = list(map(int,readline().split()))

M = 401
MOD = 10**9+7

powsum = []
for i in range(M):
    res = [pow(j,i,MOD) for j in range(M)]
    for j in range(1,M):
        res[j] = (res[j]+res[j-1])%MOD
    powsum.append(res)

dp = [0]*(c+1) # dp[i][k] = i まで見て k次斉次式
dp[0] = 1

for ai,bi in zip(a,b):
    ndp = [0]*(c+1)
    for k in range(c+1):
        for j in range(k+1):
            ndp[k] += (powsum[j][bi]-powsum[j][ai-1])*dp[k-j]%MOD
        ndp[k] %= MOD

    dp = ndp

print((dp[c]%MOD))




# キャンディーと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(401)] for i in range(401)]
for i in range(401):
    for j in range(401):
        pow_table[i][j] = pow(i, j, mod)

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_table[j][cnt+1]
        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)

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

import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7

N,C = list(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)



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

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 = []
lb = max(B)+1
for j in range(C+1):
    ac = [0]*lb
    ac[0] = 1
    for i in range(1, lb):
        ac[i] = (ac[i-1] + pow(i, j, MOD)) % MOD
    acsq.append(ac)
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])

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
exponen=[[0 for j in range(401)]for i in range(401)]
for i in range(401):
    exponen[i][0]=1
    for j in range(400):
        exponen[i][j+1]=(exponen[i][j]*i)%mod
expsum=[[0 for j in range(401)] for i in range(402)]
for j in range(401):
    for i in range(401):
        expsum[i+1][j]=(expsum[i][j]+exponen[i][j])%mod
func=[[0 for j in range(C+1)] for i in range(N)]
dp=[[0 for j in range(C+1)] for i in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(C+1):
        func[i][j]=(expsum[B[i]+1][j]-expsum[A[i]][j])%mod
for i in range(N):
    for x in range(C+1):
        for y in range(C+1):
            if (x+y>C):
                continue
            dp[i+1][x+y]+=dp[i][x]*func[i][y]
            dp[i+1][x+y]%=mod
print(dp[N][C])

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

B_max=max(B)
P=[[0]*(C+1) for _ in range(B_max+1)]

for x in range(B_max+1):
    E=P[x]
    E[0]=1
    t=1
    for k in range(1,C+1):
        E[k]=t=(t*x)%Mod

T=[]
for i in range(N):
    U=[0]*(C+1)
    for x in range(A[i],B[i]+1):
        for k in range(C+1):
            U[k]+=P[x][k]
            U[k]%=Mod
    T.append(U)

P=[1]+[0]*C
for Q in T:
    X=[0]*(C+1)

    for i in range(C+1):
        for j in range(C+1):
            if i+j>C:
                break
            X[i+j]+=P[i]*Q[j]
            X[i+j]%=Mod
    P=X.copy()

print(X[C])

mod = 10**9+7
N, C = list(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]
            S[i][j]%=mod
            power[x]*=x
            power[x]%=mod
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[i][j]%=mod
print((dp[-2][-1]))



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[0][0]=1
mod=10**9+7
X=[[0] for i in range(401)]
for i in range(401):
  for j in range(401):
    X[i].append((X[i][j]+pow(j,i,mod))%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[k][B[i]+1]-X[k][A[i]])+DP[i+1][j])%mod
print(DP[N][C])

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

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

mod=10**9+7

table=[[0 for i in range(401)] for j in range(401)]
for i in range(401):
    S=0
    for j in range(1,401):
        S+=pow(j,i,mod)
        S%=mod
        table[i][j]=S

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


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

for i in range(C+1):
    dp[0][i]=table[i][B[0]]-table[i][A[0]-1]
    dp[0][i]%=mod

for i in range(1,N):
    for j in range(C+1):
        dp[i][j]=sum(dp[i-1][j-k]*(table[k][B[i]]-table[k][A[i]-1]) for k in range(j+1))
        dp[i][j]%=mod

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

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] * (410) for _ in range(c+1)]
for i in range(c + 1):
    for j in range(409):
        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])

import sys
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))


N,C = MI()
A,B = [0]+LI(),[0]+LI()
mod = 10**9+7

X = [[0]*401 for _ in range(401)]
# X[k][l] = 0**k+1**k+…+l**k
for k in range(401):
    for l in range(1,401):
        X[k][l] = X[k][l-1]+pow(l,k,mod)
        X[k][l] %= mod

dp = [[0]*(C+1) for _ in range(N+1)]
# dp[i][j] = 子供1~iに合計j個の飴を配るときの答え
dp[0][0] = 1
for i in range(1,N+1):
    a,b = A[i],B[i]
    for j in range(C+1):
        x = 0
        for k in range(j+1):
            x += dp[i-1][j-k]*(X[k][b]-X[k][a-1])
            x %= mod
        dp[i][j] = x

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


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


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)
        ru[cnt][x + 1] %= 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])

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

N, C = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
P = 10**9+7
Y = [[pow(i, j, P) for j in range(401)] for i in range(401)]
for i in range(1, 401):
    for j in range(401):
        Y[i][j] = (Y[i][j] + Y[i-1][j]) % P
X = [[0] * (C+1) for _ in range(N+1)]
X[0][0] = 1
for i in range(1, N+1):
    for j in range(C+1):
        X[i][j] = sum([X[i-1][k] * (Y[B[i-1]][j-k] - Y[A[i-1]-1][j-k]) % P for k in range(j+1)]) % P
print(X[N][C])

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, f in enumerate(e):
    dp[i+1, j:] += dp[i, :c+1-j]*f
    dp[i+1, j:] %= MOD
ans = dp[n, c]
print(ans)

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)

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

B_max=max(B)
P=[[0]*(C+1) for _ in range(B_max+1)]

for x in range(B_max+1):
    E=P[x]
    E[0]=1
    t=1
    for k in range(1,C+1):
        E[k]=t=(t*x)%Mod

T=[]
for i in range(N):
    U=[0]*(C+1)
    for x in range(A[i],B[i]+1):
        for k in range(C+1):
            U[k]+=P[x][k]
            U[k]%=Mod
    T.append(U)

P=[1]+[0]*C
for Q in T:
    X=[0]*(C+1)

    for i in range(C+1):
        for j in range(C+1):
            if i+j>C:
                break
            X[i+j]+=P[i]*Q[j]
            X[i+j]%=Mod
    P=X.copy()

print(X[C])

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 = [[0]*(401) for _ in [0]*401]  # p[i][j]でj^i
    for i in range(401):
        for j in range(401):
            p[i][j] = pow(j, i, mod)

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


main()

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(A[i], B[i] + 1):
        x = 1
        for k in range(C+1):
            X[k] = (X[k] + x) % mod
            x = x * j % 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])

def main1(n,c,a,b):
  mod=10**9+7
  # a[0],..,a[n-1]がそれぞれ無限個ある。重複有で好きにc個選んで積を取った時の和。
  # dp[i+1][j]:idx=iまでの中から好きにj個選んで積を取った時の和。
  # a[i]~b[i]を同時に計算する。
  dp=[[0]*(c+1) for i in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    ary=[0]*(b[i]+1-a[i])
    tmp=0
    for j in range(c+1):
      tmp+=dp[i][j]*(b[i]+1-a[i])
      tmp%=mod
      dp[i+1][j]+=tmp
      dp[i+1][j]%=mod
      tmp=0
      for k in range(b[i]+1-a[i]):
        ary[k]+=dp[i][j]
        ary[k]*=a[i]+k
        ary[k]%=mod
        tmp+=ary[k]
        tmp%=mod
  return dp[n][c]

def __starting_point():
  n,c=map(int,input().split())
  a=list(map(int,input().split()))
  b=list(map(int,input().split()))
  print(main1(n,c,a,b))
__starting_point()

import numpy as np
N, C = list(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]))