You are situated in an $n$ dimensional grid at position $\left(x[1],x[2],\ldots,x[n]\right)$. The dimensions of the grid are $(D[1],D[2],...D[n])$. In one step, you can walk one step ahead or behind in any one of the $n$ dimensions. This implies that there are always $2\times n$ possible moves if movements are unconstrained by grid boundaries. How many ways can you take $m$ steps without leaving the grid at any point? You leave the grid if at any point $x[i]$, either $x[i]\leq0$ or $x[i]>D[i]$.

For example, you start off in a 3 dimensional grid at position $x=[2,2,2]$.  The dimensions of the grid are $D=[3,3,3]$, so each of your axes will be numbered from $1$ to $3$.  If you want to move $m=1$ step, you can move to the following coordinates: $\{[1,2,2],[2,1,2],[2,2,1],[3,2,2],[2,3,2],[2,2,3]\}$.    

If we started at $x=[1,1,1]$ in the same grid, our new paths would lead to $\{[1,1,2],[1,2,1],[2,1,1]\}$.  Other moves are constrained by $x[i]\not\leq0$.

Function Description

Complete the gridWalking function in the editor below.  It should return an integer that represents the number of possible moves, modulo $(10^9+7)$.

gridWalking has the following parameter(s):

m: an integer that represents the number of steps  
x: an integer array where each $x[i]$ represents a coordinate in the $i^{\mbox{th}}$ dimension where $1\leq i\leq n$
D: an integer array where each $D[i]$ represents the upper limit of the axis in the $i^{\mbox{th}}$ dimension  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.

Each of the next $\boldsymbol{\boldsymbol{t}}$ sets of lines is as follows:

The first line contains two space-separated integers, $n$ and $m$.  
The next line contains $n$ space-separated integers $x[i]$.  
The third line of each test contains $n$ space-separated integers $D[i]$.  

Constraints

$1\leq t\leq10$
$1\leq n\leq10$  
$1\leq m\leq300$  
$1\leq D[i]\leq100$  
$1\leq x[i]\leq D[i]$  

Output Format

Output one line for each test case. Since the answer can be really huge, output it modulo $10^9+7$.  

Sample Input
1
2 3
1 1
2 3

Sample Output
12

Explanation

We are starting from (1, 1) in a $2\times3$ 2-D grid, and need to count the number of possible paths with length equal to $3$. 

Here are the $12$ paths:

$(1,1)\rightarrow(1,2)\rightarrow(1,1)\rightarrow(1,2)$ 

$(1,1)\to(1,2)\to(1,1)\to(2,1)$ 

$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(1,2)$ 

$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)$ 

$(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(1,2)$ 

$(1,1)\to(1,2)\to(2,2)\to(2,1)$ 

$(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)$ 

$(1,1)\rightarrow(2,1)\rightarrow(1,1)\rightarrow(1,2)$ 

$(1,1)\rightarrow(2,1)\rightarrow(1,1)\rightarrow(2,1)$ 

$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,1)$ 

$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(1,2)$ 

$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)$  

$12\mod(10^9+7)=12$

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


MOD = 10 ** 9 + 7

def main():
	ncases = int(input())
	for case in range(ncases):
		(ndim, nmoves) = readints()
		x = readints()
		d = readints()
		assert ndim == len(x) == len(d)
		print(solve(nmoves, x, d))

def readints():
	return list(map(int, input().split()))

def solve(m, x, d):
	prev = [1] + [0] * m
	for (x1, d1) in zip(x, d):
		curr = []
		newdim = comb1d(m, 1 - x1, d1 - x1)
		for i in range(m + 1):
			paths = 0
			comb = 1
			for j in range(i + 1):
				paths = (paths + prev[j] * newdim[i - j] * comb) % MOD
				comb = comb * (i - j) * pow(j + 1, MOD - 2, MOD) % MOD
			curr.append(paths)
		prev = curr
	return curr[-1]

def comb1d(m, a, b):
	if not a <= 0 <= b:
		return [0] * (m + 1)
	tbl = [{n: 1 for n in range(max(-m, a), min(m, b) + 1)}]
	for seqlen in range(1, m + 1):
		lo = max(seqlen - m, a)
		hi = min(m - seqlen, b)
		newrow = {}
		prevrow = tbl[-1]
		prevrow[a - 1] = prevrow[b + 1] = 0
		for i in range(lo, hi + 1):
			newrow[i] = (prevrow[i - 1] + prevrow[i + 1]) % MOD
		tbl.append(newrow)
	return [row[0] for row in tbl]
main()


mod = 1000000007
ncr = [[0] * (n + 1) for n in range(301)]
for n in range(301):
	ncr[n][0] = ncr[n][n] = 1
	for r in range(1, n):
		ncr[n][r] = ncr[n - 1][r] + ncr[n - 1][r - 1]
T = int(input())
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	x = [int(i) - 1 for i in input().split()]
	D = [int(i) for i in input().split()]
	paths = [[[0 for _ in range(D[n])] for m in range(M + 1)] for n in range(N)]
	for n in range(N):
		paths[n][0][x[n]] = 1
		if D[n] > 1:
			for m in range(1, M + 1):
				paths[n][m][0] = paths[n][m - 1][1]
				paths[n][m][-1] = paths[n][m - 1][-2]
				for k in range(1, D[n] - 1):
					paths[n][m][k] = (paths[n][m - 1][k - 1] + paths[n][m - 1][k + 1]) % mod
	path_counts = [[sum(paths[n][m]) % mod for m in range(M + 1)] for n in range(N)]
	results = [[0 for _ in range(M + 1)] for _ in range(N)]
	results[0] = path_counts[0]
	for n in range(1, N):
		for m in range(M + 1):
			for k in range(m + 1):
				results[n][m] = (results[n][m] + ncr[m][k] * path_counts[n][k] * results[n - 1][m - k]) % mod
	print(results[-1][-1])


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


MOD = 1000000007
t = eval(input())

def predict(x, d, value):
	return x + value if x + value <= d and x + value >= 1 else x
combi = [[1] * (300 + 1) for i in range(300 + 1)]
for i in range(1, 300 + 1):
	for j in range(1, i + 1):
		if j >= i // 2 + 1:
			combi[i][j] = combi[i][i - j]
		else:
			combi[i][j] = combi[i - 1][j - 1] + combi[i - 1][j]
			combi[i][j] %= MOD

def fact(n):
	return 1 if n == 0 else n * fact(n - 1) % MOD

def comb(n, c):
	result = 1
	for i in range(c):
		result *= n - i
		result //= i + 1
		result %= MOD
	return result
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	x1 = list(map(int, input().split()))
	x2 = list(x1)
	d = list(map(int, input().split()))
	count = [[0] * (d[i] + 1) for i in range(n)]
	for i in range(n):
		count[i][x1[i]] = 1
	newCount = [[0] * (d[i] + 1) for i in range(n)]
	med = [[1] * (m + 1) for i in range(n)]
	for temp in range(m):
		for i in range(n):
			for j in range(x2[i], x1[i] + 1):
				if j + 1 <= d[i]:
					newCount[i][j + 1] += count[i][j]
				if j - 1 >= 1:
					newCount[i][j - 1] += count[i][j]
		for i in range(n):
			if x1[i] + 1 <= d[i]:
				x1[i] += 1
			if x2[i] - 1 >= 1:
				x2[i] -= 1
		for i in range(n):
			curSum = 0
			for j in range(d[i] + 1):
				count[i][j] = newCount[i][j]
				curSum = curSum + count[i][j]
				newCount[i][j] = 0
			med[i][temp + 1] = curSum
	calc = [[0] * (m + 1) for i in range(n)]
	sum = 0
	for i in range(n):
		for j in range(m + 1):
			if i > 0:
				for mid in range(j + 1):
					calc[i][j] += calc[i - 1][mid] * med[i][j - mid] * combi[j][mid]
			else:
				calc[i][j] = med[i][j]
	print(calc[n - 1][m] % MOD)


def grid_walking(N, M, X, D):
	W = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
	for i in range(N):
		T = [[0 for _ in range(M + 1)] for _ in range(D[i] + 1)]
		for j in range(1, D[i] + 1):
			T[j][0] = 1
		for j in range(1, M + 1):
			for k in range(1, D[i] + 1):
				if k - 1 > 0:
					T[k][j] += T[k - 1][j - 1]
					T[k][j] %= 1000000007
				if k + 1 <= D[i]:
					T[k][j] += T[k + 1][j - 1]
					T[k][j] %= 1000000007
		W[0][i + 1] = 1
		for j in range(1, M + 1):
			W[j][i + 1] = T[X[i]][j]
	C = [[0 for _ in range(M + 1)] for _ in range(M + 1)]
	for i in range(M + 1):
		C[i][0] = 1
		C[i][i] = 1
	for i in range(1, M + 1):
		for j in range(1, i):
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
			C[i][j] %= 1000000007
	T = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
	for i in range(M + 1):
		T[i][1] = W[i][1]
	for i in range(N + 1):
		T[0][i] = 1
	for i in range(2, N + 1):
		for j in range(1, M + 1):
			T[j][i] = 0
			for k in range(j + 1):
				T[j][i] += C[j][j - k] * T[k][i - 1] * W[j - k][i]
				T[j][i] %= 1000000007
	return T[M][N]

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(v) for v in input().split()]
		X = [int(v) for v in input().split()]
		D = [int(v) for v in input().split()]
		print(grid_walking(N, M, X, D))
main()


import math

def solve_one_dim(pos, m, length):
	length += 1
	result = []
	result.append(1)
	record = [2 for x in range(length)]
	record[1] -= 1
	record[-1] -= 1
	result.append(record[pos])
	for i in range(2, m + 1):
		index = 1
		next = []
		next.append(None)
		while index < length:
			tmp = 0
			if index - 1 > 0:
				tmp += record[index - 1]
			if index + 1 < length:
				tmp += record[index + 1]
			next.append(tmp % 1000000007)
			index += 1
		record = next
		result.append(record[pos])
	return result

def get_d_walk(pos, dim, m):
	d_walk = []
	for i in range(len(pos)):
		row = solve_one_dim(pos[i], m, dim[i])
		d_walk.append(row)
	return d_walk

def n_c_k(n, k):
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

def get_nm(walk, d_walk, j, i):
	tmp = 0
	for k in range(0, j + 1):
		tmp += walk[i - 1][k] * d_walk[i][j - k] * n_c_k(j, k)
	return tmp

def get_walk(d_walk, n_size, m):
	walk = []
	walk.append(d_walk[0])
	for i in range(1, n_size):
		row = []
		row.append(1)
		for j in range(1, m + 1):
			nm = get_nm(walk, d_walk, j, i)
			row.append(nm)
		walk.append(row)
	return int(walk[n_size - 1][m] % 1000000007)
size = int(input().strip())
for i in range(size):
	line = input().strip().split(' ')
	n_size = int(line[0])
	m = int(line[1])
	pos = list(map(int, input().strip().split(' ')))
	dim = list(map(int, input().strip().split(' ')))
	d_walk = get_d_walk(pos, dim, m)
	print(get_walk(d_walk, n_size, m))


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
ncr_max = 310
ncr = [[0] * ncr_max for _ in range(ncr_max)]
for i in range(ncr_max):
	ncr[i][0] = ncr[i][i] = 1
	for j in range(1, i):
		ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % mod

@memoize
def get_single_dim_path(dim, x, currM):
	if not 0 <= x < dim:
		return 0
	if currM == 0:
		return 1
	return (get_single_dim_path(dim, x + 1, currM - 1) + get_single_dim_path(dim, x - 1, currM - 1)) % mod
T = int(input())
for case in range(T):
	(N, M) = map(int, input().split(' '))
	xarr = [int(s) - 1 for s in input().rstrip().split(' ')]
	darr = list(map(int, input().rstrip().split(' ')))

	@memoize
	def solve(k, currM):
		if k == N:
			return 1 if currM == 0 else 0
		res = 0
		for i in range(currM + 1):
			r = get_single_dim_path(darr[k], xarr[k], i) * ncr[currM][i]
			res += r * solve(k + 1, currM - i)
		return res % mod
	print(solve(0, M))


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


tableCnK = {}

def CnK(n, k):
	if k == 0:
		return 1
	if k == 1:
		return n
	if (n, k) not in tableCnK:
		tableCnK[n, k] = CnK(n, k - 1) * (n - k + 1) // k
	return tableCnK[n, k]
table = {}

def PathsInOneDim(x, steps, max_x):
	global table
	if x > max_x or x < 1:
		return 0
	if steps == 0:
		return 1
	if (x, steps) not in table:
		if min(max_x - x, x - 1) >= steps:
			table[x, steps] = 2 ** steps
		else:
			table[x, steps] = PathsInOneDim(x - 1, steps - 1, max_x) + PathsInOneDim(x + 1, steps - 1, max_x)
	return table[x, steps]

def sol(start, M, dims):
	global table
	dptable1 = [[1] * (M + 1) for _ in range(len(dims))]
	for k in range(len(dims)):
		table = {}
		for m in range(1, M + 1):
			dptable1[k][m] = PathsInOneDim(start[k], m, dims[k])
	dptable2 = [dptable1[0], [1] * (M + 1)]
	index = 1
	for k in range(1, len(dims)):
		for m in range(1, M + 1):
			count = 0
			for m_in_dim_k in range(m + 1):
				a = dptable2[1 - index][m - m_in_dim_k]
				b = dptable1[k][m_in_dim_k]
				count += a * b * CnK(m, m_in_dim_k)
			dptable2[index][m] = count
		index = 1 - index
	return dptable2[1 - index][M]
t = int(input())
for test in range(t):
	(_, m) = map(int, input().split())
	start = tuple(map(int, input().split()))
	dims = list(map(int, input().split()))
	print(sol(start, m, dims) % 1000000007)


def f(di, xi, m):
	if not hasattr(f, 'cache'):
		f.cache = [None] * 101
	if f.cache[di] == None:
		f.cache[di] = [[-1] * 301 for i in range(di + 1)]
	if m == 0:
		res = 1
	else:
		if f.cache[di][xi][m] == -1:
			f.cache[di][xi][m] = (f(di, xi - 1, m - 1) if xi > 0 else 0) + (f(di, xi + 1, m - 1) if xi < di - 1 else 0)
		res = f.cache[di][xi][m]
	return res

def k(m, j):
	if not hasattr(k, 'cache'):
		k.cache = [[-1] * 300 for i in range(300)]
	if m <= j:
		res = 1
	elif j == 1:
		res = m
	else:
		if k.cache[m - 1][j - 1] == -1:
			k.cache[m - 1][j - 1] = k(m - 1, j - 1) + k(m - 1, j)
		res = k.cache[m - 1][j - 1]
	return res

def fd(n, m, x, d, cache):
	if cache == None:
		cache = [[None] * 301 for i in range(11)]
	if cache[n][m] == None:
		if n == 1:
			cache[n][m] = f(d[0], x[0], m)
		else:
			cache[n][m] = f(d[n - 1], x[n - 1], m) + fd(n - 1, m, x, d, cache)
			for j in range(1, m):
				cache[n][m] += f(d[n - 1], x[n - 1], m - j) * fd(n - 1, j, x, d, cache) * k(m, j)
	return cache[n][m]
for i in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	x = [int(i) - 1 for i in input().split()]
	d = [int(i) for i in input().split()]
	print(fd(n, m, x, d, None) % 1000000007)


from collections import defaultdict
import sys
input1 = '1\n2 3\n1 1\n2 3\n'
input2 = '10\n1 287\n44\n78\n1 236\n25\n87\n1 122\n41\n63\n1 260\n7\n64\n1 127\n3\n73\n1 69\n6\n68\n1 231\n14\n63\n1 236\n13\n30\n1 259\n38\n70\n1 257\n11\n12\n'
input3 = '10\n7 33\n51 20 18 58 22 69 19\n62 61 24 82 91 97 78\n1 227\n8\n25\n5 69\n3 6 1 19 6\n6 13 1 27 17\n9 230\n29 11 25 2 26 7 11 2 6\n47 48 52 32 58 13 15 13 13\n1 170\n45\n90\n6 42\n10 49 32 46 4 1\n21 88 39 71 57 7\n10 138\n2 1 10 43 8 14 7 7 34 1\n6 18 46 74 74 90 8 58 72 1\n9 239\n19 9 54 63 16 14 4 13 16\n26 75 58 94 71 18 70 23 74\n2 263\n56 92\n83 93\n8 16\n18 42 8 14 9 36 54 15\n22 75 48 32 38 55 99 82\n'
input4 = '1\n4 1\n1 1 1 1\n1 1 1 1\n'

def moves(n, d):
	if n == 1:
		if d == 1:
			return [0]
		else:
			return [1] + [2] * (d - 2) + [1]
	else:
		pm = moves(n - 1, 4)
		nm = [0] * d
		for i in range(d):
			if i == 0:
				nm[i] = pm[i + 1]
			elif i == d - 1:
				nm[i] = pm[i - 1]
			else:
				nm[i] = pm[i + 1] + pm[i - 1]
		return nm

def movesmap(m, d):
	moves = [None] * m
	moves[0] = [1] + [2] * (d - 2) + [1]
	for i in range(1, m):
		moves[i] = [moves[i - 1][1]] + [moves[i - 1][j - 1] + moves[i - 1][j + 1] for j in range(1, d - 1)] + [moves[i - 1][d - 2]]
	return moves

def dmp(m):
	for r in m:
		print(r)
from math import factorial

def cnk(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)

def processTk(M, D, Xs):
	Xs = [Xs[_] for (_, d) in enumerate(D) if d > 1]
	D = [_ for _ in D if _ > 1]
	if len(D) == 0:
		return 0
	pms = [None] * len(D)
	for i in range(len(D)):
		mm = movesmap(M, D[i])
		pms[i] = [mm[_][Xs[i] - 1] for _ in range(M)]
	return mixprod(pms)
_D = {}

def calcComb(pm, dimi, avsteps):
	k = '%d-%d' % (dimi, avsteps)
	if k in _D:
		return _D[k]
	ret = 0
	if avsteps == 0:
		ret = 1
	elif dimi == 1:
		ret = pm[avsteps - 1][dimi - 1]
	else:
		ret = 0
		for stepi in range(avsteps + 1):
			if stepi == 0:
				comb = calcComb(pm, dimi - 1, avsteps - stepi)
			else:
				comb = calcComb(pm, dimi - 1, avsteps - stepi) * pm[stepi - 1][dimi - 1] * cnk(avsteps, stepi)
			ret += comb
	_D[k] = ret
	return ret

def mixprod(pms):
	D = len(pms)
	M = len(pms[0])
	pm = [[0 for _ in range(D)] for _ in range(M)]
	for i in range(D):
		for j in range(M):
			pm[j][i] = pms[i][j]
	combs = calcComb(pm, D, M)
	return combs
input = input4
input = sys.stdin.read()
lines = input.split('\n')
T = int(lines[0])
i = 0
i += 1
for _ in range(T):
	_D = {}
	(N, M) = [int(_) for _ in lines[i].split(' ')]
	i += 1
	x = [int(_) for _ in lines[i].split(' ')]
	i += 1
	D = [int(_) for _ in lines[i].split(' ')]
	i += 1
	ret = processTk(M, D, x)
	print(ret % 1000000007)


MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def solveInner(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways

def solve():
	T = int(input())
	c = {}
	for _ in range(T):
		(N, M) = list(map(int, input().split()))
		X = list(map(int, input().split()))
		D = list(map(int, input().split()))
		singles = solveInner(N, M, D)
		res = [singles[0][i][X[0] - 1] for i in range(M + 1)]
		for i in range(1, N):
			for j in range(1, M + 1)[::-1]:
				k = j
				while k >= 0 and (j, k) not in c:
					c[j, k] = choose(j, k)
					k -= 1
				res[j] = sum((res[k] * c[j, k] * singles[i][j - k][X[i] - 1] for k in range(j + 1)))
		print(res[M] % MOD)
solve()


def nCk(n, k):
	if k >= 0 and k <= n:
		ntok = 1
		ktok = 1
		T = min(k, n - k) + 1
		for t in range(1, T):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def CalculateD(StartingPoint, Dim, N, M):
	D = [[0] * (M + 1) for _ in range(N)]
	for n in range(N):
		if Dim[n] == 1:
			D[n][0] = 1
			continue
		arr = [0] * (Dim[n] + 1)
		arr[StartingPoint[n]] = 1
		D[n][0] = 1
		for m in range(1, M + 1):
			narr = [0] * (Dim[n] + 1)
			for i in range(1, Dim[n] + 1):
				if arr[i] > 0:
					if i == 1:
						narr[i + 1] += arr[i]
					elif i == Dim[n]:
						narr[i - 1] += arr[i]
					else:
						narr[i + 1] += arr[i]
						narr[i - 1] += arr[i]
			D[n][m] = sum(narr)
			arr = narr
	return D

def CalculateF(D, N, M):
	F = [[0] * (M + 1) for _ in range(N)]
	for m in range(M + 1):
		F[0][m] = D[0][m]
	nck = [[0] * (m + 1) for m in range(M + 1)]
	for m in range(1, M + 1):
		for i in range(m + 1):
			nck[m][i] = nCk(m, i)
	for n in range(1, N):
		F[n][0] = 1
		for m in range(1, M + 1):
			toSum = [0] * (m + 1)
			for i in range(m + 1):
				toSum[i] = nck[m][i] * D[n][i] * F[n - 1][m - i]
			F[n][m] = sum(toSum)
	return F
T = int(input())
for _ in range(T):
	(N, M) = tuple(map(int, input().split()))
	StartingPoint = tuple(map(int, input().split()))
	Dimensions = tuple(map(int, input().split()))
	D = CalculateD(StartingPoint, Dimensions, N, M)
	F = CalculateF(D, N, M)
	print(F[N - 1][M] % 1000000007)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


from math import factorial
MOD = 1000000007
T = int(input())
pascal = []

def pascal_line(n):
	line = [1]
	for k in range(n):
		line.append(line[k] * (n - k) // (k + 1))
	return line
for i in range(305):
	pascal.append(pascal_line(i))

def binomial(N, K):
	return pascal[N][K]
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	start = list(map(int, input().split(' ')))
	dimensions = list(map(int, input().split(' ')))
	for d in range(N):
		size_of_dimension = dimensions[d]
		L = []
		for i in range(size_of_dimension):
			L.append([])
			for length_of_path in range(M + 1):
				L[-1].append(0)
		for length_of_path in range(M + 1):
			for i in range(size_of_dimension):
				if length_of_path == 0:
					L[i][length_of_path] = 1
				else:
					if i > 0:
						L[i][length_of_path] += L[i - 1][length_of_path - 1]
					if i < size_of_dimension - 1:
						L[i][length_of_path] += L[i + 1][length_of_path - 1]
		here = L[start[d] - 1]
		if d == 0:
			last = L[start[d] - 1]
		else:
			newLast = []
			for length_of_path in range(0, M + 1):
				total = 0
				for length_of_path_in_new_dimension in range(length_of_path + 1):
					length_of_path_in_old_dimensions = length_of_path - length_of_path_in_new_dimension
					total += last[length_of_path_in_old_dimensions] * here[length_of_path_in_new_dimension] * binomial(length_of_path, length_of_path_in_new_dimension)
				newLast.append(total)
			last = newLast
	print(last[-1] % MOD)


import functools
import math
import sys
MOD = 1000000007
RD = []

@functools.lru_cache(maxsize=None)
def c(n, k):
	return math.factorial(n) // (math.factorial(k) * math.factorial(n - k)) % MOD

@functools.lru_cache(maxsize=None)
def walks_one_dimension(low, high, steps):
	if steps == 0:
		return 1
	n = 0
	if low > 0:
		n_l = min(low - 1, steps - 1)
		n_h = min(high + 1, steps - 1)
		n += walks_one_dimension(n_l, n_h, steps - 1)
	if high > 0:
		n_l = min(low + 1, steps - 1)
		n_h = min(high - 1, steps - 1)
		n += walks_one_dimension(n_l, n_h, steps - 1)
	return n % MOD

@functools.lru_cache(maxsize=None)
def walks(d, steps):
	if d == 1:
		return RD[0][steps] % MOD
	return sum([c(steps, i) * RD[d - 1][steps - i] * walks(d - 1, i) for i in range(steps + 1)]) % MOD
n_cases = int(sys.stdin.readline())
for i in range(n_cases):
	(n, steps) = map(int, sys.stdin.readline().split())
	pos = map(int, sys.stdin.readline().split())
	sizes = map(int, sys.stdin.readline().split())
	RD = []
	walks.cache_clear()
	for (p, s) in zip(pos, sizes):
		low = min(p - 1, steps)
		high = min(s - p, steps)
		RD.append([walks_one_dimension(low, high, i) for i in range(steps + 1)])
	print(walks(n, steps))


MOD = 1000000007
Paths = []
Solve = []
Choose = []
p = []
s = []
N = 0
M = 0

def C(n, k):
	if n == 0 or k == 0 or k >= n:
		return 1
	if Choose[n][k] != -1:
		return Choose[n][k]
	result = C(n - 1, k - 1) + C(n - 1, k)
	result %= MOD
	Choose[n][k] = result
	return result

def paths(idx, position, m):
	if position < 0 or position >= s[idx]:
		return 0
	if m == 0:
		return 1
	if Paths[idx][position][m] != -1:
		return Paths[idx][position][m]
	result = paths(idx, position + 1, m - 1) + paths(idx, position - 1, m - 1)
	result %= MOD
	Paths[idx][position][m] = result
	return result

def solve(idx, m):
	if m < 0:
		return 0
	if idx == N:
		if m == 0:
			return 1
		else:
			return 0
	if Solve[idx][m] != -1:
		return Solve[idx][m]
	result = 0
	for i in range(0, m + 1):
		result += C(m, i) * paths(idx, p[idx], i) * solve(idx + 1, m - i)
		result %= MOD
	Solve[idx][m] = result
	return result
T = int(input().strip())
for i in range(T):
	(N, M) = map(int, input().strip().split(' '))
	p = list(map(int, input().strip().split(' ')))
	p = [i - 1 for i in p]
	s = list(map(int, input().strip().split(' ')))
	Paths = [[[-1 for m in range(M + 1)] for position in range(max(s) + 1)] for idx in range(N + 1)]
	Solve = [[-1 for m in range(M + 1)] for idx in range(N + 1)]
	Choose = [[-1 for n in range(333)] for k in range(333)]
	print(solve(0, M))


MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
c = {}
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	X = list(map(int, input().split()))
	D = list(map(int, input().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys, math
MODULO = 10 ** 9 + 7

class Memoize(object):

	def __init__(self, function):
		self.func = function
		self.memo = dict()

	def __call__(self, *args):
		if args not in self.memo:
			try:
				self.memo[args] = self.func(*args)
			except MemoryError:
				print('NOOOO')
		return self.memo[args]

@Memoize
def choose(a, b):
	f = math.factorial
	return f(a) // f(b) // f(a - b) % MODULO

@Memoize
def walksInOne(M, x, d, i):
	if M == 0:
		return 1
	answer = 0
	if x + 1 <= d:
		answer += walksInOne(M - 1, x + 1, d, i)
	if x - 1 > 0:
		answer += walksInOne(M - 1, x - 1, d, i)
	return answer % MODULO

@Memoize
def walksInMany(M, X, D, i):
	if i == 0:
		return walksInOne(M, X[i], D[i], i)
	if M == 0:
		return 1
	answer = 0
	for m in range(0, M + 1):
		a = walksInMany(m, X, D, i - 1)
		b = walksInOne(M - m, X[i], D[i], i)
		c = choose(M, m)
		answer += a * b * c % MODULO
	return answer % MODULO
for _ in range(int(input())):
	(N, M) = tuple(map(int, input().split()))
	X = tuple(map(int, input().split()))
	D = tuple(map(int, input().split()))
	for dimension in range(0, N):
		for moves in range(0, M + 1):
			walksInOne(moves, X[dimension], D[dimension], dimension)
	for i in range(0, N):
		walksInMany(M, X, D, i)
	print(walksInMany(M, X, D, N - 1))


import sys
DEBUG = 0
if DEBUG:
	handler = open('./input')
else:
	handler = sys.stdin
cases = int(handler.readline())
MOD = 1000000007

def mirror(grid, upper_bound):
	ret = list(grid)
	for i in range(len(grid)):
		if ret[i] * 2 > upper_bound[i] + 1:
			ret[i] = upper_bound[i] + 1 - grid[i]
	return tuple(ret)
mem_1 = {}
mem_2 = {}
cache = {}

def calc_single(pos, upper_bound, moves):
	if (pos, upper_bound, moves) in mem_1:
		return mem_1[pos, upper_bound, moves]
	if moves == 0:
		return 1
	ret = 0
	if pos > 1:
		tmp = pos - 1
		if tmp * 2 > upper_bound + 1:
			tmp = upper_bound + 1 - tmp
		ret += calc_single(tmp, upper_bound, moves - 1)
	if pos < upper_bound:
		tmp = pos + 1
		if tmp * 2 > upper_bound + 1:
			tmp = upper_bound + 1 - tmp
		ret += calc_single(tmp, upper_bound, moves - 1)
	mem_1[pos, upper_bound, moves] = ret % MOD
	return ret

def cmb(n, k):
	if k * 2 > n:
		k = n - k
	if k == 0:
		return 1
	if (n, k) in mem_2:
		return mem_2[n, k]
	mem_2[n, k] = (cmb(n - 1, k - 1) + cmb(n - 1, k)) % MOD
	return mem_2[n, k]

def calc_total(start, limits, steps):
	dimensions = len(start)
	if (dimensions, steps) in cache:
		return cache[dimensions, steps]
	if dimensions == 1:
		ret = calc_single(start[0], limits[0], steps) % MOD
		cache[dimensions, steps] = ret
		return ret
	ret = 0
	for s in range(steps + 1):
		ret += cmb(steps, s) * calc_single(start[-1], limits[-1], s) * calc_total(start[:-1], limits[:-1], steps - s)
		ret %= MOD
	cache[dimensions, steps] = ret
	return cache[dimensions, steps]
for _ in range(cases):
	(dimensions, steps) = map(int, handler.readline().split())
	start = tuple(map(int, handler.readline().split()))
	limits = tuple(map(int, handler.readline().split()))
	start = mirror(start, limits)
	print(calc_total(start, limits, steps))
	cache.clear()
handler.close()


def cal(loc, dim, n, m):
	if m == 0:
		return 1
	ans = 0
	for (i, x) in enumerate(loc):
		for step in [-1, 1]:
			if 0 < x + step <= dim[i]:
				curr = loc.copy()
				curr[i] = x + step
				ans += cal(curr, dim, n, m - 1)
	return ans

def dimension(x, d, m):
	curr = [0] * d
	curr[x - 1] = 1
	ans = [1]
	for _ in range(1, m + 1):
		next = list()
		for i in range(d):
			next.append((curr[i - 1] if i > 0 else 0) + (curr[i + 1] if i < d - 1 else 0))
		ans.append(sum(next))
		curr = next
	return ans
cache = dict()

def combi(n, k):
	if n in cache and k in cache[n]:
		return cache[n][k]
	ans = 1
	for i in range(k):
		ans *= n - i
	for i in range(k):
		ans //= i + 1
	if n not in cache:
		cache[n] = dict()
	if k not in cache[n]:
		cache[n][k] = ans
	return ans

def path(d, n, m, curr):
	if m == 0:
		return 1
	if curr == n - 1:
		return d[curr][m]
	ans = 0
	for step in range(m + 1):
		ans += d[curr][step] * path(d, n, m - step, curr + 1) * combi(m, step)
	return ans % 1000000007

def path_new(d, n, m):
	ans = list()
	ans.append(d[0])
	for i in range(1, n):
		line = [1]
		for j in range(1, m + 1):
			c = 0
			for k in range(j + 1):
				c += ans[i - 1][k] * d[i][j - k] * combi(j, k)
			line.append(c)
		ans.append(line)
	return ans
for _ in range(int(input().strip())):
	(n, m) = [int(x) for x in input().strip().split()]
	start = [int(x) for x in input().strip().split()]
	dim = [int(x) for x in input().strip().split()]
	d = list()
	for i in range(n):
		d.append(dimension(start[i], dim[i], m))
	print(path_new(d, n, m)[n - 1][m] % 1000000007)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import collections
import math

def read_input():
	(dimension_count, steps) = get_int_list(input())
	initial_position = get_int_list(input())
	grid_dimensions = get_int_list(input())
	return (dimension_count, steps, initial_position, grid_dimensions)

class Solution:

	def __init__(self):
		(self.dimension_count, self.steps, self.initial_position, grid_dimensions) = read_input()
		self.initial_position = tuple(self.initial_position)
		self.grid_dimensions = grid_dimensions
		self.graph = self.create_graph()
		self.mod_val = 1000000007

	def create_graph(self):
		graph = []
		for i in range(self.dimension_count):
			graph_dimens = {}
			for grid in range(1, self.grid_dimensions[i] + 1):
				graph_dimens[grid] = []
				for b in [-1, 1]:
					new_pos = grid + b
					if 0 < new_pos <= self.grid_dimensions[i]:
						graph_dimens[grid].append(new_pos)
			graph.append(graph_dimens)
		return graph

	def calculate(self):
		return self.grid_walk()

	def grid_walk(self):
		combined_positions = None
		for i in range(self.dimension_count):
			position = self.get_1d_paths_array(i)
			position_array = []
			for j in range(self.steps + 1):
				position_array.append(sum(position[j].values()))
			combined_positions = self.combine_positions(position_array, combined_positions)
		return combined_positions[self.steps] % self.mod_val

	def combine_positions(self, position, combined_positions):
		if combined_positions is None:
			combined_positions = position
		else:
			combined_positions_old = combined_positions
			combined_positions = [None] * (self.steps + 1)
			combined_positions[0] = 1
			for path_len in range(1, self.steps + 1):
				sum = 0
				for len1 in range(0, path_len + 1):
					sum += position[len1] * combined_positions_old[path_len - len1] * self.get_choose(path_len, len1)
				combined_positions[path_len] = sum % self.mod_val
		return combined_positions

	def get_choose(self, n, k):
		return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

	def get_1d_paths_array(self, index):
		position = []
		position.append({self.initial_position[index]: 1})
		for step in range(self.steps):
			position.append(collections.defaultdict(int))
			for (origin, value) in position[step].items():
				for destination in self.graph[index][origin]:
					position[step + 1][destination] = (position[step + 1][destination] + value) % self.mod_val
		return position

def main():
	cases = int(input())
	for i in range(cases):
		my_object = Solution()
		print(my_object.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


import math
T = int(input().strip())
MOD = 1000000007

def aux(array):
	new = [0 for _ in array]
	new[0] = array[1]
	new[-1] = array[-2]
	for i in range(1, len(array) - 1):
		new[i] = array[i - 1] + array[i + 1]
	return new

def oneDimension(pos, d, m):
	if d < 2:
		temp = [0 for _ in range(m + 1)]
		temp[0] = 1
		return temp
	array = [0 for _ in range(d)]
	array[pos] = 1
	partial = [1]
	for _ in range(m):
		array = aux(array)
		partial.append(sum(array))
	return partial

def nCr(n, r):
	return int(math.factorial(n) // math.factorial(r) // math.factorial(n - r)) % MOD

def combine(a1, a2, M):
	ans = []
	for n in range(0, M + 1):
		total = 0
		for i in range(0, n + 1):
			next = a1[i] * a2[n - i] * nCr(n, i) % MOD
			total = (total + next) % MOD
		ans.append(total)
	return ans
for testCase in range(0, T):
	(N, M) = (int(x) for x in input().strip().split(' '))
	pos = [int(x) - 1 for x in input().strip().split(' ')]
	Ds = [int(x) for x in input().strip().split(' ')]
	current = oneDimension(pos[0], Ds[0], M)
	for i in range(1, N):
		if Ds[i] >= 2:
			current = combine(current, oneDimension(pos[i], Ds[i], M), M)
	print(current[-1] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import math
inputs = []
use_file = False
if use_file:
	with open('input.txt', 'r') as f:
		t = int(f.readline().strip())
		for _t in range(t):
			(n, m) = [int(x) for x in f.readline().split()]
			X = [int(x) - 1 for x in f.readline().split()]
			D = [int(x) for x in f.readline().split()]
			inputs.append([n, m, X, D])
else:
	t = int(input().strip())
	for _t in range(t):
		(n, m) = [int(x) for x in input().split()]
		X = [int(x) - 1 for x in input().split()]
		D = [int(x) for x in input().split()]
		inputs.append([n, m, X, D])
memoize_fact = {}

def fast_fact(big, small):
	if (big, small) not in memoize_fact:
		memoize_fact[big, small] = math.factorial(big) // math.factorial(small) // math.factorial(big - small) % 1000000007
	return memoize_fact[big, small]

def uniquePaths(pos, dim_start, dim_end, steps, d_map, memoize_table):
	if (dim_start, dim_end, steps) in memoize_table:
		return memoize_table[dim_start, dim_end, steps]
	elif dim_start == dim_end:
		return d_map[dim_start][steps][pos[dim_start]]
	else:
		sum = 0
		for i in range(steps + 1):
			sum += fast_fact(steps, i) * uniquePaths(pos, dim_start, int((dim_start + dim_end) / 2), i, d_map, memoize_table) * uniquePaths(pos, int((dim_start + dim_end) / 2) + 1, dim_end, steps - i, d_map, memoize_table) % 1000000007
		memoize_table[dim_start, dim_end, steps] = sum % 1000000007
		return sum
for (n, m, X, D) in inputs:
	memoize_table = {}
	d_map = []
	for i in range(len(D)):
		D_i = [[1 for x in range(D[i])] for y in range(m + 1)]
		for step in range(1, len(D_i)):
			for loc in range(len(D_i[step])):
				if loc == 0 and len(D_i[step]) == 1:
					D_i[step][loc] = 0
				elif loc == 0:
					D_i[step][loc] = D_i[step - 1][loc + 1] % 1000000007
				elif loc == len(D_i[step]) - 1:
					D_i[step][loc] = D_i[step - 1][loc - 1] % 1000000007
				else:
					D_i[step][loc] = (D_i[step - 1][loc + 1] + D_i[step - 1][loc - 1]) % 1000000007
		d_map.append(D_i)
	print(uniquePaths(X, 0, n - 1, m, d_map, memoize_table) % 1000000007)


import math

def choose(n, k):
	assert n >= k, 'k should be smaller or equal than n'
	assert k >= 0, 'k should be >= 0'
	return math.factorial(n) // math.factorial(n - k) // math.factorial(k)

def countWalk1D(D, M, i0):
	S = [[0] * D for i in range(M)]
	A = [0] * (M + 1)
	if i0 > 0:
		S[0][i0 - 1] = 1
	if i0 < D - 1:
		S[0][i0 + 1] = 1
	A[0] = 1
	A[1] = sum(S[0])
	for m in range(1, M):
		j = max(0, i0 - (m + 1))
		while j < D and j - i0 <= m + 1:
			S_left = S[m - 1][j - 1] if j > 0 else 0
			S_right = S[m - 1][j + 1] if j < D - 1 else 0
			S[m][j] = S_left + S_right
			j += 1
		A[m + 1] = sum(S[m])
	return A

def countWalk(D, M, i0):
	Anext = countWalk1D(D[0], M, i0[0] - 1)
	if len(D) == 1:
		print(int(Anext[-1]) % 1000000007)
		return
	for i in range(1, len(D)):
		Adim = countWalk1D(D[i], M, i0[i] - 1)
		Aold = list(Anext)
		start = 1 if i < len(D) - 1 else M
		for m in range(start, M + 1):
			Anext[m] = 0
			for m2 in range(0, m + 1):
				Anext[m] += choose(m, m2) * Aold[m2] * Adim[m - m2]
	total_walks = Anext[-1]
	print(int(total_walks) % 1000000007)
T = int(input())
while T:
	aux = [int(s) for s in input().split()]
	M = aux[1]
	i0 = [int(s) for s in input().split()]
	D = [int(s) for s in input().split()]
	countWalk(D, M, i0)
	T -= 1


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


def grid_walking(startpos, maxpos, maxsteps):
	mod = 1000000007
	one_d = []
	for dim in range(len(maxpos)):
		table = [list([1] + [0] * maxsteps) for _ in range(maxpos[dim])]
		for steps in range(1, maxsteps + 1):
			for pos in range(1, maxpos[dim]):
				table[pos][steps] = table[pos - 1][steps - 1]
			for pos in range(maxpos[dim] - 1):
				table[pos][steps] += table[pos + 1][steps - 1]
				table[pos][steps] %= mod
		one_d.append(table[startpos[dim] - 1])
	all_d = [one_d[0]]
	for dim in range(1, len(maxpos)):
		all_d.append([1] + [0] * maxsteps)
		for steps in range(1, maxsteps + 1):
			perms = 1
			for i in range(steps + 1):
				all_d[dim][steps] += perms * one_d[dim][i] * all_d[dim - 1][steps - i]
				perms *= steps - i
				perms //= i + 1
			all_d[dim][steps] %= mod
	return all_d[-1][-1]
for _ in range(int(input())):
	(_, maxsteps) = [int(x) for x in input().split()]
	startpos = [int(x) for x in input().split()]
	maxpos = [int(x) for x in input().split()]
	answer = grid_walking(startpos, maxpos, maxsteps)
	print(answer)


def fillOneDWalks(walksOneD, maxPoint):
	for size in maxPoint:
		if size in walksOneD:
			continue
		walksOneD[size] = walks1D(size, steps)

def walks1D(size, steps):
	walks = [[0 for s in range(0, steps + 1)] for origin in range(0, size + 1 + 1)]
	for origin in range(1, size + 1):
		walks[origin][0] = 1
	for step in range(1, steps + 1):
		for origin in range(1, size + 1):
			walks[origin][step] = walks[origin - 1][step - 1] + walks[origin + 1][step - 1]
	return walks

def stepMix(maxSteps):
	mix = [[0 for ss in range(0, maxSteps + 1)] for s in range(0, maxSteps + 1)]
	for ss in range(0, maxSteps + 1):
		mix[1][ss] = ss + 1
		mix[ss][1] = ss + 1
	for s in range(2, maxSteps + 1):
		mix[s][0] = 1
		mix[0][s] = 1
		for ss in range(s, maxSteps + 1):
			combination = 0
			for space in range(ss, -1, -1):
				combination += mix[s - 1][space]
			mix[s][ss] = combination
			mix[ss][s] = mix[s][ss]
	return mix

def gridWalks(dimensionQty, steps, origin, maxPoint, walksOneD, mixSteps):
	walks = [[0 for s in range(0, steps + 1)] for d in range(0, dimensionQty + 1)]
	for d in range(1, dimensionQty + 1):
		for s in range(1, steps + 1):
			dimSize = maxPoint[d - 1]
			dimOrigin = origin[d - 1]
			walks[d][s] = walks[d - 1][s]
			walks[d][s] += walksOneD[dimSize][dimOrigin][s]
			for dimStep in range(1, s):
				lowerDimStep = s - dimStep
				combinedWalks = walksOneD[dimSize][dimOrigin][dimStep] * walks[d - 1][lowerDimStep] * mixSteps[dimStep][lowerDimStep]
				walks[d][s] += combinedWalks
	return walks
tests = int(input())
for t in range(0, tests):
	(dimensionQty, steps) = [int(i) for i in input().split(' ')]
	origin = [int(o) for o in input().split(' ')]
	maxPoint = [int(mo) for mo in input().split(' ')]
	walksOneD = {}
	fillOneDWalks(walksOneD, maxPoint)
	mixSteps = stepMix(steps)
	walks = gridWalks(dimensionQty, steps, origin, maxPoint, walksOneD, mixSteps)
	walkCount = walks[dimensionQty][steps]
	print(walkCount % 1000000007)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


(M, F, IF) = (10 ** 9 + 7, [1] * 301, [1] * 301)

def powM(b, e):
	return b if e == 1 else powM(b, e >> 1) ** 2 * b % M if e & 1 else powM(b, e >> 1) ** 2 % M
for i in range(2, 301):
	F[i] = F[i - 1] * i % M
	IF[i] = powM(F[i], M - 2)

def C(n, m):
	return F[n] * IF[n - m] % M * IF[m] % M
(CP, rs, prs, crs) = ([[0] * (301 - i) for i in range(301)], [0] * 301, [0] * 301, [0] * 301)

def buildDim(x, d, m, rs):
	for i in range(m + 1):
		rs[i] = 0
	for i in range(m + 1):
		for j in range(m - i + 1):
			CP[i][j] = 0
	for i in range(0, x):
		CP[i][0] = 1
		rs[i] += 1
	for i in range(1, d - x + 1):
		CP[0][i] = 1
		rs[i] += 1
	for k in range(1, m + 1):
		for i in range(1, k):
			if i - (k - i) < x and k - i - i < d - x + 1:
				CP[i][k - i] = (CP[i - 1][k - i] + CP[i][k - i - 1]) % M
				rs[k] = (rs[k] + CP[i][k - i]) % M
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	(x, D) = ([int(x) for x in input().rstrip().split(' ')], [int(x) for x in input().rstrip().split(' ')])
	buildDim(x[0], D[0], m, rs)
	for i in range(1, n):
		buildDim(x[i], D[i], m, crs)
		for i in range(m + 1):
			prs[i] = 0
		for a in range(m + 1):
			for b in range(m - a + 1):
				prs[a + b] = (prs[a + b] + C(a + b, a) * crs[a] % M * rs[b]) % M
		(rs, prs) = (prs, rs)
	print(rs[m])


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import functools
import math
import sys
MOD = 1000000007
RD = []

@functools.lru_cache(maxsize=None)
def c(n, k):
	return math.factorial(n) // (math.factorial(k) * math.factorial(n - k)) % MOD

@functools.lru_cache(maxsize=None)
def walks_one_dimension(low, high, steps):
	if steps == 0:
		return 1
	n = 0
	if low > 0:
		n_l = min(low - 1, steps - 1)
		n_h = min(high + 1, steps - 1)
		n += walks_one_dimension(n_l, n_h, steps - 1)
	if high > 0:
		n_l = min(low + 1, steps - 1)
		n_h = min(high - 1, steps - 1)
		n += walks_one_dimension(n_l, n_h, steps - 1)
	return n % MOD

@functools.lru_cache(maxsize=None)
def walks(d, steps):
	if d == 1:
		return RD[0][steps] % MOD
	return sum([c(steps, i) * RD[d - 1][steps - i] * walks(d - 1, i) for i in range(steps + 1)]) % MOD
n_cases = int(sys.stdin.readline())
for i in range(n_cases):
	(n, steps) = map(int, sys.stdin.readline().split())
	pos = map(int, sys.stdin.readline().split())
	sizes = map(int, sys.stdin.readline().split())
	RD = []
	walks.cache_clear()
	for (p, s) in zip(pos, sizes):
		low = min(p - 1, steps)
		high = min(s - p, steps)
		RD.append([walks_one_dimension(low, high, i) for i in range(steps + 1)])
	print(walks(n, steps))


import math
mod = 1000000007

def grid_walking(m, x, D):
	n = len(x)
	d_move = d_movement(x, D, m)
	result = []
	result.append(d_move[0])
	for z in range(n - 1):
		comb = [1]
		k = 0
		for i in range(len(result[z]) - 1):
			k = k + 1
			d = 0
			t = 0
			for j in range(k, -1, -1):
				t += result[z][d] * d_move[z + 1][j] * (math.factorial(i + 1) // (math.factorial(i + 1 - d) * math.factorial(d)))
				d = d + 1
			comb.append(t)
		result.append(comb)
	return result[n - 1][m] % mod

def d_movement(x, D, m):
	dim_results = []
	for i in range(len(x)):
		pos = x[i]
		limit = D[i] + 1
		result = [1]
		count = [2 for k in range(limit)]
		count[1] -= 1
		count[-1] -= 1
		result.append(count[pos])
		for k in range(2, m + 1):
			new = [0]
			count_pos = 1
			while count_pos < limit:
				temp = 0
				if count_pos - 1 > 0:
					temp += count[count_pos - 1]
				if count_pos + 1 < limit:
					temp += count[count_pos + 1]
				new.append(temp)
				count_pos += 1
			count = new
			result.append(new[pos] % mod)
		dim_results.append(result)
	return dim_results

def comb_dim(res, mov):
	comb = [1]
	k = 0
	for i in range(len(res) - 1):
		k = k + 1
		d = 0
		t = 0
		for j in range(k, -1, -1):
			t += res[d] * mov[j] * (math.factorial(i + 1) // (math.factorial(i + 1 - d) * math.factorial(d)))
			d = d + 1
		comb.append(t)
	return comb
t = int(input())
for t in range(t):
	(n, M) = map(int, input().split())
	x = list(map(int, input().split()))[:n]
	D = list(map(int, input().split()))[:n]
	print(grid_walking(M, x, D))


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)


T = int(input())
MOD = 1000000007
C = [[0] * 400 for _ in range(400)]
C[0][0] = 1
for i in range(400):
	(C[i][0], C[i][i]) = (1, 1)
	for j in range(1, i):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for t in range(T):
	(N, M) = [int(c) for c in input().split()]
	X = [int(c) for c in input().split()]
	D = [int(c) for c in input().split()]
	dp = [[[0] * (M + 1) for j in range(D[i])] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			dp[i][j][0] = 1
			if j > 0:
				dp[i][j][1] += 1
			if j < D[i] - 1:
				dp[i][j][1] += 1
		for m in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					dp[i][j][m] += dp[i][j - 1][m - 1]
				if j < D[i] - 1:
					dp[i][j][m] += dp[i][j + 1][m - 1]
	total = [dp[0][X[0] - 1][m] for m in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			total[j] = sum((total[k] * C[j][k] * dp[i][X[i] - 1][j - k] for k in range(j + 1)))
	print(total[M] % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q

def count_ways(N, M, D):
	ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
	for i in range(N):
		for j in range(D[i]):
			ways[i][0][j] = 1
			if j > 0:
				ways[i][1][j] += 1
			if j < D[i] - 1:
				ways[i][1][j] += 1
		for s in range(2, M + 1):
			for j in range(D[i]):
				if j > 0:
					ways[i][s][j] += ways[i][s - 1][j - 1]
				if j < D[i] - 1:
					ways[i][s][j] += ways[i][s - 1][j + 1]
	return ways
T = int(sys.stdin.readline())
c = {}
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	X = list(map(int, sys.stdin.readline().split()))
	D = list(map(int, sys.stdin.readline().split()))
	ways = count_ways(N, M, D)
	total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
	for i in range(1, N):
		for j in reversed(range(1, M + 1)):
			k = j
			while k >= 0 and (j, k) not in c:
				c[j, k] = choose(j, k)
				k -= 1
			total[j] = sum((total[k] * c[j, k] * ways[i][j - k][X[i] - 1] for k in range(j + 1)))
	print(total[M] % MOD)