Maya is teaching Alex about HyperText Markup Language (HTML). Alex is confused about div and span tags, so Maya decides to reduce the concept to a simpler visual by representing div tags as square brackets and span tags as parentheses. In other words, she represents <div> as [, </div> as ], <span> as (, and </span> as ).

We use the following rules to determine the validity of a configuration:

The empty string (""), a single pair of square brackets [], and single pair of parentheses () are all considered to be valid configurations. We can express each of these as ${V}$.
A valid configuration, ${V}$, which does not contain square brackets is called a normal configuration, which we can express as $N$. For example, () is normal.
Two or more consecutive valid configurations (e.g., ${VV}$) also constitute a valid configuration. For example, [][], ()(), and []()[] are all valid.
The following configurations are also valid: [V], (N). 

For example, [[(())]()], ((())), and [(())[]] are all valid; however, ([]) is not valid (you cannot nest a div tag inside a span tag).

Given some number of distinguishable square brackets, ${X}$, and some number of distinguishable parentheses, ${Y}$, how many valid configurations can we build using the above rules? As this answer can be very large, print it modulo $10^9+7$.

Input Format

The first line contains a single positive integer, ${T}$, denoting the number of test cases. 

Each of the ${T}$ subsequent lines contains $2$ positive space-separated integers describing the respective values of ${X}$ (the number of distinguishable square brackets) and $Y$ (the number of distinguishable parentheses).

Constraints

$1\leq T\leq1000$
$1\leq X\leq10^5$
$1\leq Y\leq200$

Output Format

For each test case, print the number of different valid configurations modulo $10^9+7$.

Sample Input
3
1 1
1 2
2 2

Sample Output
3
18
160

Explanation

For the first test case, $X=1$, $Y=1$, these are $3$ valid configurations: 

[]()
()[]
[()]

Thus, we print the result of $3\%(10^9+7)$ on the first line.

For the second test case, if brackets and parentheses were not distinguishable, we would have only $\mbox{9}$ different configurations:

[()]() []()() [](())
()[]() [()()] [(())]
()()[] ()[()] (())[]

However, they are distinguishable, so [](1)(2) is not same as [](2)(1) (where (1) and (2) are the respective first and second pairs of parentheses. For this reason, we have $18}$ possible configurations and print the result of $18\%(10^9+7)$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


MOD = 10 ** 9 + 7
f = [1]
for i in range(1, 200002):
	f.append(f[-1] * i % MOD)

def inv(x):
	return pow(x, MOD - 2, MOD)

def Cnk(n, k):
	if n < k:
		return 0
	return f[n] * inv(f[k] * f[n - k]) % MOD
catalan_cache = {}

def catalan(n):
	if n in catalan_cache:
		return catalan_cache[n]
	result = f[2 * n] * inv(f[n] * f[n + 1]) % MOD
	catalan_cache[n] = result
	return result
c = [catalan(i) for i in range(401)]
fi = [inv(f[i]) for i in range(401)]
sum_m_is_n_cache = {}

def catalan_sum_m_is_n(n, m):
	if n not in sum_m_is_n_cache:
		sum_m_is_n_cache[n] = {}
	if m in sum_m_is_n_cache[n]:
		return sum_m_is_n_cache[n][m]
	if m == 1:
		return c[n]
	if m == 2:
		return c[n + 1]
	if m == 3:
		return c[n + 2] - c[n + 1]
	m2 = m // 2
	if m % 2 == 0:
		top = m2 * f[n + m2 - 1] * f[n + m2 + 1] % MOD
	else:
		top = m * f[n + m2] * f[n + m2 + 1] % MOD
	bottom = fi[n] * fi[n + m] % MOD
	result = top * bottom * c[n + m2] % MOD
	sum_m_is_n_cache[n][m] = result
	return result
catalan_sum_cache = {}

def exactly_m_subsets_from_n_brace_pairs(n, m):
	if n not in catalan_sum_cache:
		catalan_sum_cache[n] = {}
	if m in catalan_sum_cache[n]:
		return catalan_sum_cache[n][m]
	result = 0
	for i in range(m, 0, -1):
		result = (result + Cnk(m, i) * catalan_sum_m_is_n(n, m=i) * pow(-1, m - i)) % MOD
	catalan_sum_cache[n][m] = result
	return result

def insertions(holes, Y):
	result = 0
	for m in range(1, min(holes, Y) + 1):
		result = (result + exactly_m_subsets_from_n_brace_pairs(Y, m) * Cnk(holes, m)) % MOD
	return result

def number(X, Y):
	return catalan(X) * f[X] * f[Y] * insertions(2 * X + 1, Y) % MOD
for _ in range(int(input())):
	(X, Y) = list(map(int, input().split()))
	print(number(X, Y))


m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


MOD = 10 ** 9 + 7
MAX_X = 10 ** 5
MAX_Y = 200
LIM = 2 * (MAX_X + MAX_Y) + 1
fact = [1] * (LIM + 1)
invfact = [1] * (LIM + 1)
inv = [1] * (LIM + 1)
for i in range(2, LIM + 1):
	fact[i] = fact[i - 1] * i % MOD
	inv[i] = (MOD - MOD // i * inv[MOD % i] % MOD) % MOD
invfact[LIM] = pow(fact[LIM], MOD - 2, MOD)
for i in range(LIM, 1, -1):
	invfact[i - 1] = invfact[i] * i % MOD

def comb(n, k):
	return fact[n] * invfact[k] * invfact[n - k] % MOD

def F(X, Y):
	catalan = comb(2 * X, X) * inv[X + 1]
	ext_catalan = (2 * X + 1) * comb(2 * (X + Y), Y) * inv[Y + 2 * X + 1]
	return catalan * ext_catalan * fact[X] * fact[Y] % MOD
T = int(input())
for t_itr in range(T):
	(X, Y) = map(int, input().split())
	print(F(X, Y))


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


mod = 1000000007
factlist = [1]
for i in range(400000):
	factlist.append(factlist[-1] * (i + 1) % mod)
factinvlist = [0] * len(factlist)
factinvlist[-1] = pow(factlist[-1], mod - 2, mod)
for i in range(len(factlist) - 1, 0, -1):
	factinvlist[i - 1] = factinvlist[i] * i % mod
numspandict = dict()
t = int(input())
for _ in range(t):
	[x, y] = list(map(int, input().split()))
	try:
		numspans = numspandict[y]
	except:
		numspans = [0] * (y + 1)
		for i in range(y):
			numspans[i + 1] = factlist[2 * (y - 1) - i] * factinvlist[y - i - 1] * y * (i + 1) * pow(y, mod - 2, mod) % mod
		numspandict[y] = numspans
	toprint = 0
	for i in range(y + 1):
		toprint += factlist[2 * x + i] * factinvlist[x + 1] * factinvlist[i] * numspans[i] % mod
	print(toprint % mod)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)


m = 10 ** 9 + 7
p_lim = 201
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
	fact.append(fact[-1] * i % m)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	r = fact[n] * modinv(fact[k], m) % m
	return r * modinv(fact[n - k], m) % m

def C(n):
	return fact[2 * n] * modinv(fact[n + 1], m) % m
for i in range(1, p_lim):
	dpp[i][1] = cumsum[i - 1] % m
	cumsum[i] = (cumsum[i] + dpp[i][1]) % m
	for j in range(2, p_lim):
		for k in range(1, i - j + 2):
			dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m
		cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	r = 0
	for i in range(y + 1):
		r += dpp[y][i] * choose(2 * x + i, i)
		r %= m
	r = r * fact[y] % m
	r = r * C(x) % m
	print(r)