Shashank is very excited after learning about the linked list. He learned about how to merge two linked lists. When we merge two linked lists, the order of the elements of each list doesn't change. For example, if we merge $[1,2,3]$ and $[4,5,6]$, $[1,4,2,3,5,6]$ is a valid merge, while $[1,4,3,2,5,6]$ is not a valid merge because $3$ appears before $2$. 

Shashank wants you to solve a problem for him: You are given two lists having sizes $N$ and $\mbox{M}$. How many ways can we merge both the lists? It is given that all $N+M$ elements are distinct. As your answer can be quite large, Shashank wants you to print it $\:\textbf{mod}\:10^9+7$. 

Input Format

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

Each of the next $\mathbf{T}$ lines contains two integers $N$ and $\mbox{M}$.  

Constraints

$1\leq T\leq10$  
$1\leq N\leq100$  
$1\leq M\leq100$  

Output Format

Print the value of the answer $\:\textbf{mod}\:10^9+7$. 

Sample Input 0
1
2 2

Sample Output 0
6

Explanation 0

Suppose the two lists are $[1,2]$ and $[3,4]$. The different ways of merging these lists are given below:

$[1,2,3,4]$ 

$[1,3,2,4]$ 

$[3,4,1,2]$ 

$[3,1,4,2]$ 

$[1,3,4,2]$ 

$[3,1,2,4]$

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ret = 1
	for i in range(n + 1, n + m + 1):
		ret *= i
	for i in range(1, m + 1):
		ret //= i
	print(ret % (10 ** 9 + 7))


import sys
from math import sqrt
memo = {}
memo[0, 0] = 1

def rec(N, M):
	if (N, M) in memo:
		return memo[N, M]
	ret = 0
	if N > 0:
		ret += rec(N - 1, M)
	if M > 0:
		ret += rec(N, M - 1)
	ret %= 1000000007
	memo[N, M] = ret
	return ret

def solve():
	stdin = sys.stdin
	write = sys.stdout.write
	t = int(stdin.readline())
	for _ in range(t):
		(n, m) = map(int, stdin.readline().split())
		write('%d\n' % rec(n, m))
solve()


import functools

@functools.lru_cache(maxsize=None)
def choose(x, N):
	if x > N / 2:
		x = N - x
	if N == 0:
		return 1
	if x == 0:
		return 1
	return choose(x, N - 1) + choose(x - 1, N - 1)

def main():
	T = int(input(''))
	for t in range(T):
		[N, M] = map(int, input('').split(' '))
		print(choose(N, M + N) % 1000000007)
main()


from sys import *

def bi(n, k):
	res = 1
	for i in range(n - k, n):
		res *= i + 1
		while k > 0 and res % k == 0:
			res //= k
			k -= 1
	return res
t = int(stdin.readline())
for i in range(t):
	[n, m] = [int(j) for j in stdin.readline().split()]
	print(bi(n + m, m) % 1000000007)


k = int(input())
for i in range(k):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	a = min(m, n)
	b = m + n
	res = 1
	for i in range(a):
		res *= b - i
		res //= i + 1
	print(res % 1000000007)


from sys import *

def bi(n, k):
	res = 1
	for i in range(n - k, n):
		res *= i + 1
		while k > 0 and res % k == 0:
			res //= k
			k -= 1
	return res
T = int(stdin.readline())
for i in range(T):
	[N, M] = [int(j) for j in stdin.readline().split()]
	print(bi(N + M, M) % 1000000007)


def Cnk(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(0, k):
		res *= n - i
		res //= i + 1
	return res

def solve(n, m):
	modulo = 10 ** 9 + 7
	return Cnk(n + m, n) % modulo
t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	print(solve(n, m))


LARGE_MOD = 10 ** 9 + 7

def binomial(n, k, mod):
	binom_array = []
	for m in range(n + 1):
		binom_array.append([])
		for i in range(m + 1):
			if i == 0 or i == m:
				binom_array[m].append(1)
			else:
				binom_array[m].append((binom_array[m - 1][i - 1] + binom_array[m - 1][i]) % mod)
	return binom_array[n][k]
num_test_cases = int(input())
for c in range(num_test_cases):
	line = input().split()
	M = int(line[0])
	N = int(line[1])
	print(binomial(M + N, N, LARGE_MOD))


import math
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split(' '))
	print(math.factorial(a + b) // (math.factorial(a) * math.factorial(b)) % (10 ** 9 + 7))


from math import factorial as f

def comb(n, k):
	return f(n) // f(k) // f(n - k)
modulo = 10 ** 9 + 7
for t in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	print(comb(n + m, m) % modulo)


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):
	(g, x, y) = egcd(a, m)
	return x % m

def facmod(a, m):
	res = 1
	for i in range(1, a + 1):
		res = res * i % m
	return res

def binmod(u, d, m):
	return facmod(u, m) * modinv(facmod(d, m) * facmod(u - d, m), m) % m
T = int(input())
for t in range(T):
	(N, M) = list(map(int, input().split()))
	print(binmod(N + M, min(N, M), 1000000007))


def calc(n, m, memo):
	if n == 0:
		return 1
	if m == 0:
		return 1
	if (n, m) in memo:
		return memo[n, m]
	res = calc(n - 1, m, memo) + calc(n, m - 1, memo)
	memo[n, m] = res
	return res
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(calc(n, m, {}) % (10 ** 9 + 7))


import math
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = max(n, m)
	b = min(n, m)
	v = math.factorial(b + a) // (math.factorial(a) * math.factorial(b))
	print(v % 1000000007)


import math
T = int(input())
for i in range(T):
	line1 = list(map(int, input().split(' ')))
	N = line1[0]
	M = line1[1]
	numerator = 1
	for i in range(N + M, M, -1):
		numerator *= i
	Nfact = math.factorial(N)
	print(numerator // Nfact % 1000000007)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	print(math.factorial(n + m) // (math.factorial(n) * math.factorial(m)) % mod)


from math import factorial

def combin(n, r):
	return factorial(n) // factorial(r) // factorial(n - r)
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	print(combin(a + b, a) % 1000000007)


import math
p = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	s = 1
	for i in range(n + m, max(m, n), -1):
		s = s * i
	s = s // math.factorial(min(m, n))
	print(s % p)


import math
mod = 10 ** 9 + 7

def binomial(n, r):
	return math.factorial(n) // math.factorial(n - r) // math.factorial(r)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(binomial(a + b, a) % mod)


numTrials = int(input())

def ordered_merge(M, N):
	return binomial_coeff(M + N, N)

def binomial_coeff(n, m):
	bc = {}
	for i in range(n + 1):
		bc[i, 0] = 1
	for j in range(n + 1):
		bc[j, j] = 1
	for i in range(1, n + 1):
		for j in range(1, i):
			bc[i, j] = bc[i - 1, j] + bc[i - 1, j - 1] % (10 ** 9 + 7)
	return bc[n, m] % (10 ** 9 + 7)
for i in range(numTrials):
	L = input().split()
	L = [int(i) for i in L]
	print(ordered_merge(L[0], L[1]))


def f(n, m, d):
	if (n, m) in d:
		return d[n, m]
	ret = 0
	if n == 0 or m == 0:
		ret = 1
	else:
		ret = f(n - 1, m, d) + f(n, m - 1, d)
	ret %= 1000000000.0 + 7
	d[n, m] = ret
	return ret
T = int(input()[0])
d = {}
while T > 0:
	(n, m) = (int(i) for i in input().split())
	print(int(f(n, m, d)))
	T -= 1


T = [[-1 for y in range(102)] for x in range(102)]
M = 10 ** 9 + 7

def ways(n, m):
	if T[n][m] != -1:
		return T[n][m]
	if n == 0 or m == 0:
		return 1
	T[n][m] = (ways(n - 1, m) + ways(min(n, m - 1), max(n, m - 1))) % M
	return T[n][m]
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	if n > m:
		(n, m) = (m, n)
	print(ways(n, m))


import math
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	Total = N + M
	Total_Fact = math.factorial(Total)
	N_Fact = math.factorial(N)
	M_Fact = math.factorial(M)
	result = Total_Fact // (N_Fact * M_Fact)
	print(result % (10 ** 9 + 7))


from math import factorial
mod = 10 ** 9 + 7
numTests = int(input())
for test in range(numTests):
	(m, n) = map(int, input().split(' '))
	print(factorial(m + n) // (factorial(m) * factorial(n)) % mod)


from operator import mul
from fractions import Fraction
from functools import reduce

def nCk(n, k):
	if k > n / 2:
		k = n - k
	return int(reduce(mul, (Fraction(n - i, i + 1) for i in range(k)), 1))
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	print(nCk(N + M, N) % (10 ** 9 + 7))


p = 1000000007
max_n = 201
factorial = [1] * max_n
inv_factorial = [1] * max_n

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

def mod_inv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m

def nCr(n, r):
	return factorial[n] * inv_factorial[r] * inv_factorial[n - r] % p
for i in range(1, max_n):
	factorial[i] = i * factorial[i - 1] % p
	inv_factorial[i] = mod_inv(i, p) * inv_factorial[i - 1] % p
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	print(nCr(m + n, m))


mod = 10 ** 9 + 7

def scan(op, seq, it):
	a = []
	result = it
	a.append(it)
	for x in seq:
		result = op(result, x)
		a.append(result)
	return a

def pascal(n):

	def nextrow(row, x):
		return [l + r for (l, r) in zip(row + [0], [0] + row)]
	return scan(nextrow, range(n - 1), [1])
P = pascal(201)
T = int(input())
for _ in range(T):
	(n, m) = [int(ns) for ns in str(input()).split()]
	print(P[m + n][m] % mod)


modulo = 10 ** 9 + 7
comb_dict = {}

def Comb(n, r):
	if r == 0 or n == r:
		return 1
	nr = (n, r)
	if nr in comb_dict:
		return comb_dict[n, r]
	comb_dict[nr] = (Comb(n - 1, r) + Comb(n - 1, r - 1)) % modulo
	return comb_dict[nr]
T = int(input())
for cnt in range(T):
	[M, N] = list(map(int, input().strip().split(' ')))
	print(Comb(M + N, N))


from math import factorial
for _ in range(int(input())):
	(N, M) = map(int, input().strip().split())
	print(factorial(N + M) // (factorial(N) * factorial(M)) % (10 ** 9 + 7))


def c(n, k):
	if k < 0 or k > n:
		return 0
	if k == 0 or k == n:
		return 1
	k = min(k, n - k)
	c = 1
	for i in range(k):
		c = c * (n - i) // (i + 1)
	return c
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(c(n + m, m) % (10 ** 9 + 7))


def factorial(N):
	if N == 0:
		return 1
	else:
		return N * factorial(N - 1)
T = int(input())
for i in range(T):
	(N, M) = tuple(map(int, input().split()))
	print(factorial(N + M) // (factorial(N) * factorial(M)) % (10 ** 9 + 7))


def fact(n):
	if n < 2:
		return 1
	return n * fact(n - 1)

def binomial(n, k):
	return fact(n) // (fact(k) * fact(n - k))
T = int(input().strip())
for t in range(T):
	(n, m) = map(int, input().strip().split())
	print(binomial(n + m, n) % 1000000007)


MOD = 1000000007
nCr = [[int(0) for x in range(0, 205)] for x in range(0, 205)]

def Preprocess():
	nCr[1][0] = 1
	nCr[1][1] = 1
	for i in range(2, 201):
		nCr[i][0] = 1
		for j in range(1, i + 1):
			nCr[i][j] = nCr[i - 1][j - 1] + nCr[i - 1][j]
			if nCr[i][j] >= MOD:
				nCr[i][j] %= MOD

def solve():
	s = input()
	(N, M) = s.strip().split()
	N = int(N)
	M = int(M)
	ans = nCr[N + M][M]
	print(ans)

def main():
	t = int(input())
	Preprocess()
	while t > 0:
		solve()
		t -= 1
main()


mod = int(1000000000.0 + 7)
fac = [1]
for i in range(200):
	fac.append(fac[i] * (i + 1) % mod)
for xx in range(int(input())):
	(n, m) = map(int, input().split())
	ans = fac[n + m] * pow(fac[n], mod - 2, mod) * pow(fac[m], mod - 2, mod) % mod
	print(ans)


from math import factorial
factorialTable = {}

def fact(x):
	if x in factorialTable:
		return factorialTable[x]
	else:
		factorialTable[x] = factorial(x)
		return factorialTable[x]
for _ in range(int(input())):
	(m, n) = list(map(int, input().split()))
	print(fact(n + m) // (fact(m) * fact(n)) % 1000000007)


modulo = 1000000007
for _ in range(int(input().strip())):
	(n, m) = map(int, input().strip().split(' '))
	currArr = [1 for i in range(m + 1)]
	for i in range(n):
		newCurr = [1]
		for j in range(1, m + 1):
			newCurr.append((newCurr[j - 1] + currArr[j]) % modulo)
		currArr = newCurr
	print(currArr[m])


import math
d = {}
d[0] = [1]
d[1] = [1, 1]
for i in range(2, 202):
	d[i - 1] = [1]
	for j in range(1, i - 1):
		d[i - 1] += [d[i - 2][j - 1] + d[i - 2][j]]
	d[i - 1] += [1]
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	print(d[n + m][n] % (10 ** 9 + 7))


from math import factorial
modulus = 10 ** 9 + 7

def modInv(num):
	temp = 1
	bitList = '{0:b}'.format(modulus - 2)
	for b in bitList:
		if b == '0':
			temp = temp * temp % modulus
		else:
			temp = temp * temp * num % modulus
	return temp

def f(val):
	temp = 1
	for i in range(1, val + 1):
		temp = temp * i % modulus
	return temp

def comp(n, k):
	return f(n - 1) * modInv(f(k - 1) * f(n - k) % modulus) % modulus
T = int(input().strip())
for testcase in range(T):
	(n, m) = [int(a) for a in input().strip().split()]
	(n, m) = [n, m] if n < m else [m, n]
	total = 0
	for k in range(1, n + 1):
		for j in range(max(1, k - 1), min(m, k + 1) + 1):
			multiplier = 2 if j == k else 1
			total = (total + multiplier * comp(n, k) * comp(m, j)) % modulus
	print(total)


import math
t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	print(math.factorial(n + m) // (math.factorial(m) * math.factorial(n)) % 1000000007)
	t -= 1


def binome(m, p):
	table = {}
	for n in range(m + 1):
		for k in range(n + 1):
			if k == 0 or n == k:
				table[n, k] = 1
			else:
				table[n, k] = (table[n - 1, k - 1] % 1000000007 + table[n - 1, k] % 1000000007) % 1000000007
	return table[m, p]
T = int(input())
for i in range(T):
	args = input()
	A = [int(i) for i in args.split()]
	print(binome(A[0] + A[1], A[0]))


from functools import reduce
modo = 10 ** 9 + 7

def prod(l):
	return reduce(lambda x, y: x * y % modo, l)

def inv(n):
	return pow(n, modo - 2, modo)
for _ in range(int(input().strip())):
	(n, m) = map(int, input().strip().split())
	print(prod(range(m + 1, m + n + 1)) * inv(prod(range(1, n + 1))) % modo)


MAX_N = 100
MAX_M = 100
MOD_NUM = 10 ** 9 + 7
solutions = [[1] * (MAX_N + 1) for _ in range(MAX_M + 1)]
for n in range(1, MAX_N + 1):
	for m in range(1, MAX_M + 1):
		solutions[n][m] = solutions[n - 1][m] + solutions[n][m - 1]
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().strip().split())
	print(solutions[N][M] % MOD_NUM)


import math
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	print(int(math.factorial(n + m) // (math.factorial(n) * math.factorial(m))) % 1000000007)


def fact(n):
	return 1 if n <= 1 else fact(n - 1) * n
cache = [[1 if i == 0 or j == 0 else -1 for i in range(100)] for j in range(100)]

def solve(n, m):
	if cache[n][m] > -1:
		return cache[n][m]
	answer = 0
	for i in range(m, -1, -1):
		answer += solve(n - 1, m)
	cache[n][m] = answer
	return answer
t = int(input())
for i in range(t):
	(n, m) = map(int, input().strip().split(' '))
	print(fact(n + m) // (fact(n) * fact(m)) % (10 ** 9 + 7))


from math import factorial as f
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(int(f(n + m) // f(n) // f(m) % mod))


def fall_mod(n, k, modulus):
	if k <= 0:
		return 1
	return fall_mod(n - 1, k - 1, modulus) * n % modulus

def binomial_mod(n, k, modulus):
	try:
		binom = fall_mod(n, k, modulus) * modinv(fall_mod(k, k, modulus), modulus) % modulus
	except ValueError:
		binom = 0
	return int(binom)

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):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
P = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(m, n) = (int(x) for x in input().split())
	print(binomial_mod(n + m, m, P))


from math import factorial
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	print(factorial(N + M) // factorial(N) // factorial(M) % (10 ** 9 + 7))


def factorial(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	ans = factorial(N + M) // (factorial(N) * factorial(M))
	print(ans % int(1000000000.0 + 7))


from math import factorial
print(*map(lambda m, n: factorial(m + n) // factorial(m) // factorial(n) % 1000000007, *zip(*(map(int, input().split()) for _ in range(int(input()))))), sep='\n')


MOD = 10 ** 9 + 7

def fact(n):
	f = 1
	while n > 0:
		f *= n
		n -= 1
	return f
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	print(fact(M + N) // fact(N) // fact(M) % MOD)


P = 10 ** 9 + 7
A = {}

def f(m, n):
	try:
		return A[m, n]
	except:
		if m == 1:
			A[m, n] = n + 1
			return n + 1
		if n == 0:
			A[m, n] = 1
			return 1
		s = 0
		for i in range(n + 1):
			s += f(m - 1, n - i)
		A[m, n] = s % P
		return s % P
for i in range(1, 101):
	for j in range(1, 101):
		f(i, j)
T = int(input())
for i in range(T):
	(n, m) = (int(j) for j in input().split())
	print(f(m, n))


from math import factorial as f
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(f(n + m) // (f(n) * f(m)) % 1000000007)


import math
T = int(input())

def nCr(n, r, q):
	f = math.factorial
	retval = f(n)
	retval //= f(r) * f(n - r)
	retval %= q
	return retval
for _ in range(T):
	(N, M) = [int(X) for X in input().strip().split(' ')]
	print(nCr(N + M, M, 10 ** (+9) + 7))


import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
MAXN = 300

def power(N, K):
	if K == 0:
		return 1
	elif K == 1:
		return N
	pw = power(N, K // 2)
	if K & 1:
		return pw * pw * N % MOD
	return pw * pw % MOD
fact = [0]
num = 1
for i in range(1, MAXN):
	num = num * i % MOD
	fact.append(num)
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	print(fact[N + M] * (power(fact[N] * fact[M] % MOD, MOD - 2) % MOD) % MOD)


def factorial(n):
	ans = 1
	for i in range(2, n + 1):
		ans *= i
	return ans

def binom(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)
T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	print(binom(N + M, N) % (10 ** 9 + 7))


casos = [[int(i) for i in input().split()] for i in range(int(input()))]
filas = [sum(i) for i in casos]
triangulo = [[1, 1]]
contador = 1
modulo = 10 ** 9
numero_filas = max(filas)
for i in range(numero_filas - 1):
	lista = [1]
	for e in range(contador):
		lista.append((triangulo[i][e] + triangulo[i][e + 1]) % (modulo + 7))
	lista.append(1)
	contador += 1
	triangulo += [lista]
for i in range(len(casos)):
	print(triangulo[filas[i] - 1][casos[i][0]])


B = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 1
	for i in range(min(m, n)):
		c = c * (m + n - i) // (i + 1)
	print(c % B)


def fac(n):
	k = 1
	for i in range(1, n + 1):
		k *= i
	return k
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	print(fac(n + m) // fac(n) // fac(m) % (10 ** 9 + 7))


T = int(input())
for _ in range(T):
	(n, m) = [int(x) for x in input().split()]
	nm = n + m
	if m > n:
		(n, m) = (m, n)
	p = 1
	for i in range(nm, n, -1):
		p = p * i
	while m > 1:
		p = p // m
		m -= 1
	print(int(p % 1000000007))


x = [None] * 101
for i in range(0, 101):
	x[i] = [None] * 101
for i in range(1, 101):
	x[i][0] = 1
	x[0][i] = 1
for i in range(1, 101):
	for j in range(1, 101):
		x[i][j] = x[i - 1][j] + x[i][j - 1]
t = int(input())
for _ in range(t):
	(p, q) = list(map(int, input().split()))
	print(x[p][q] % 1000000007)


import math
t = int(input())
for i in range(t):
	(a, b) = input().strip().split(' ')
	(a, b) = (int(a), int(b))
	s = a + b
	f = math.factorial(s) // (math.factorial(s - a) * math.factorial(s - b))
	print(f % 1000000007)


from math import factorial
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))


B = 1000000007
c = [[0 for i in range(202)] for i in range(202)]
for i in range(1, 200):
	c[1][i] = i
	c[i][1] = i
	c[0][i] = 1
	c[i][0] = 1
	c[i][i] = 1
c[0][0] = 1
for i in range(2, 201):
	for j in range(2, 201):
		if i == j:
			c[i][j] = 1
		else:
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % B
t = int(input())
while t != 0:
	t -= 1
	(a, b) = [int(x) for x in input().split()]
	print(c[a + b][b])


def fact(m, n):
	x = max(n, m)
	y = min(n, m)
	num = int(1)
	den = int(1)
	for _ in range(x + 1, x + y + 1, 1):
		num = num * _
	for _ in range(1, y + 1, 1):
		den = den * _
	num1 = num // den % (10 ** 9 + 7)
	return num1
t = int(input())
r = []
for t0 in range(t):
	(m, n) = map(int, input().split())
	r.append(fact(n, m))
for i in range(t):
	print(int(r[i]))


t = int(input())
mod = 1000000007

def merge(t, mod):
	while t > 0:
		t -= 1
		(n, m) = map(int, input().strip().split())
		dividers = n + 1
		circles = m
		N = dividers + circles - 1
		k = circles
		ans = ncr(N, k, mod)
		ans %= mod
		print(ans)

def ncr(n, k, mod):
	dp = [0] * (k + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, k), 0, -1):
			dp[j] += dp[j - 1]
			dp[j] %= mod
	return dp[k]
merge(t, mod)


from math import factorial
t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	ans = factorial(n + m) // (factorial(n) * factorial(m))
	ans = ans % 1000000007
	print(ans)


from math import factorial
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))


T = int(input())
for _ in range(T):
	(n, m) = [int(x) for x in input().split()]
	nm = n + m
	if m > n:
		(n, m) = (m, n)
	p = 1
	for i in range(nm, n, -1):
		p = p * i
	while m > 1:
		p = p // m
		m -= 1
	print(int(p % 1000000007))


U = {}

def parts(n, l):
	if (n, l) in U:
		return U[n, l]
	if l == 1:
		return 1
	if n == 0:
		return 1
	s = 0
	for i in range(0, n + 1):
		s += parts(n - i, l - 1)
	s = s % (10 ** 9 + 7)
	U[n, l] = s
	return s
T = int(input())
for t0 in range(T):
	(N, M) = (int(a) for a in input().split())
	P = parts(M, N + 1)
	print(P)


from math import factorial as fac
T = int(input())
desc = 10 ** 9 + 7
for _ in range(T):
	(N, M) = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	temp_res = 1
	for index in range(M + 1, N + M + 1):
		temp_res *= index
	for index in range(1, N + 1):
		temp_res = temp_res // index
	res = int(temp_res % desc)
	print(res)


ctest = int(input())
for itest in range(ctest):
	tokens = input().split()
	N = int(tokens[0])
	M = int(tokens[1])
	prod = 1
	for k in range(M + 1, N + M + 1):
		prod *= k
	for k in range(1, N + 1):
		prod //= k
	print(prod % (10 ** 9 + 7))


import functools
import itertools
import operator
import math
from collections import Counter

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)

def main():
	test_count = int(input())
	for __ in range(test_count):
		(n, m) = [int(x) for x in input().strip().split(' ')]
		print(nCr(n + m, n) % (10 ** 9 + 7))
main()


import math
t = int(input())
i = 0
while i < t:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	print(math.factorial(m + n) // (math.factorial(m) * math.factorial(n)) % 1000000007)
	i = i + 1


n = int(input())
max = 0
psl = [[1]]
for i in range(n):
	(num1, num2) = input().strip().split(' ')
	(num1, num2) = [int(num1), int(num2)]
	inp = num1 + num2
	if inp > max:
		for j in range(max + 1, inp + 1):
			psl.append([])
			for k in range(j + 1):
				if k == 0:
					psl[j].append(1)
				elif k == j:
					psl[j].append(1)
				else:
					l = int(psl[j - 1][k - 1]) + int(psl[j - 1][k])
					psl[j].append(l % (10 ** 9 + 7))
		max = inp
	print(psl[inp][num1])


from math import factorial
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))


import math
for _ in range(int(input())):
	(m, n) = input().split()
	(m, n) = (int(m), int(n))
	print(math.factorial(m + n) // (math.factorial(m) * math.factorial(n)) % 1000000007)


mod = 10 ** 9 + 7
l = []
for i in range(101):
	temp = list((0 for i in range(101)))
	l.append(temp)
for i in range(101):
	l[0][i] = 1
	l[i][0] = 1
for i in range(1, 101):
	for j in range(1, 101):
		l[i][j] = (l[i - 1][j] + l[i][j - 1]) % mod
for t in range(int(input())):
	(a, b) = map(int, input().split())
	print(l[a][b])


import sys
from math import factorial
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split(' ')]
	print(int(factorial(m + n) // (factorial(m) * factorial(n)) % 1000000007))


from math import factorial
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(N, M) = [int(tmp) for tmp in input().split(' ')]
	print(factorial(N + M) // factorial(N) // factorial(M) % mod)


from math import factorial
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))


def f(n):
	return 1 if n <= 1 else f(n - 1) * n
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(f(x + y) // f(x) // f(y) % (10 ** 9 + 7))


import math
for _ in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	print(math.factorial(n + m) // math.factorial(n) // math.factorial(m) % (10 ** 9 + 7))


T = int(input())
for t in range(T):
	n = list(map(int, input().split()))
	N = n[0] + n[1]
	combiArr = []
	for i in range(N + 1):
		combiArr.append([])
		for j in range(i + 1):
			if j == 0 or j == i:
				presentValue = 1
			else:
				presentValue = combiArr[i - 1][j - 1] + combiArr[i - 1][j]
			combiArr[i].append(presentValue)
	div = pow(10, 9) + 7
	print(combiArr[N][n[0]] % div)


T = int(input())
for _ in range(T):
	(n, m) = [int(x) for x in input().split()]
	nm = n + m
	if m > n:
		(n, m) = (m, n)
	p = 1
	for i in range(nm, n, -1):
		p = p * i
	while m > 1:
		p = p // m
		m -= 1
	print(int(p % 1000000007))


from math import factorial
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))


def phi(a, b):
	if a < 1 or b < 1:
		return 1
	elif a == 1:
		return b + 1
	elif a < b:
		return phi(a - 1, b) * (a + b) // a
	elif a == b:
		return 2 * phi(a - 1, b)
	elif a > b:
		return phi(b, a)
mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	inp = input().split(' ')
	(n, m) = [int(inp[0]), int(inp[1])]
	print(phi(n, m) % mod)


T = int(input())
for _ in range(T):
	(n, m) = [int(x) for x in input().split()]
	nm = n + m
	if m > n:
		(n, m) = (m, n)
	p = 1
	for i in range(nm, n, -1):
		p = p * i
	while m > 1:
		p = p // m
		m -= 1
	print(int(p % 1000000007))


from math import factorial as f

def ncr(n, r):
	return f(n) // (f(n - r) * f(r))
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	print(ncr(m + n, n) % (10 ** 9 + 7))


from math import factorial
t = input()
for _ in range(int(t)):
	(m, n) = map(int, input().split())
	print(factorial(m + n) // factorial(m) // factorial(n) % (10 ** 9 + 7))


from sys import stdin
readl = stdin.readline
mod = 10 ** 9 + 7

def ncr(n, r):
	from functools import reduce
	from operator import mul
	r = min(r, n - r)
	nom = reduce(mul, range(n, n - r, -1), 1)
	denom = reduce(mul, range(1, r + 1), 1)
	return nom // denom
for _ in range(int(readl())):
	(n, m) = map(int, readl().split())
	print(ncr(n + m, n) % mod)


import math

def combinations2(a, b):
	return math.factorial(a + b) // (math.factorial(a) * math.factorial(b))
t = int(input().strip())
for i in range(t):
	(n, m) = (int(j) for j in input().strip().split(' '))
	print(combinations2(n, m) % (10 ** 9 + 7))


def H(n, r):
	return C(n + r - 1, r)

def C(n, r):
	if r == 0:
		return 1
	if r == 1:
		return n
	if n - r < r:
		r = n - r
	nn = n - r + 1
	rr = 1
	R = 1
	while rr <= r:
		R = R * nn // rr
		nn += 1
		rr += 1
	return R % (10 ** 9 + 7)
t = int(input())
for _ in range(t):
	(n1, n2) = list(map(int, input().split()))
	r = H(n1 + 1, n2)
	print(r)


from math import factorial as fac
T = int(input().strip())
for t in range(T):
	(n, m) = input().strip().split()
	(N, M) = (int(n), int(m))
	print(fac(N + M) // fac(N) // fac(M) % (10 ** 9 + 7))


from math import factorial as fact
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(fact(n + m) // (fact(n) * fact(m)) % 1000000007)


from math import factorial
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))


mod = 10 ** 9 + 7
T = int(input())
N = []
M = []
for t in range(T):
	(n, m) = map(int, input().split())
	N.append(n)
	M.append(m)
Nmax = max(N) + 1
Mmax = max(M) + 1
grid = [[0] * Mmax for i in range(Nmax)]
for n in range(Nmax):
	grid[n][0] = 1
for m in range(Mmax):
	grid[0][m] = 1
for n in range(1, Nmax):
	for m in range(1, Mmax):
		grid[n][m] = (grid[n - 1][m] + grid[n][m - 1]) % mod
for t in range(T):
	print(grid[N[t]][M[t]])


t = int(input())
mm = 10 ** 9 + 7
inverses = [0] * 101
powers = [1 << i for i in range(32)]

def inverse(n):
	ret = 1
	power = n
	ex = mm - 2
	while ex > 0:
		if ex & 1:
			ret = ret * power % mm
		ex >>= 1
		power = power * power % mm
	return ret
inverses[0] = 1
for i in range(1, 101):
	inverses[i] = inverse(i) * inverses[i - 1] % mm

def binom(n, k):
	ret = 1
	for head in range(n - k + 1, n + 1):
		ret = ret * head % mm
	return ret * inverses[k] % mm
for it in range(t):
	(m, n) = [int(x) for x in input().split()]
	print(binom(m + n, n) if m > n else binom(m + n, m))


t = int(input())
for _ in range(t):
	(m, n) = list(map(int, input().split()))
	res = 1
	div = 1
	for i in range(1, n + 1):
		res *= i + m
		div *= i
	print(res // div % (10 ** 9 + 7))


T = int(input())
p = 10 ** 9 + 7
F = [1, 1]
for i in range(2, 205):
	F.append(F[i - 1] * i % p)
for _ in range(T):
	(n, m) = [int(a) for a in input().strip().split(' ')]
	print(F[n + m] * pow(F[n], p - 2, p) * pow(F[m], p - 2, p) % p)


MOD = 10 ** 9 + 7
T = int(input())
for run in range(T):
	(n, m) = [int(i) for i in input().split()]
	(p, q) = (1, 1)
	for i in range(m):
		p *= n + i + 1
		q *= i + 1
	print(p // q % MOD)


from math import factorial
t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	print(factorial(n + m) // factorial(n) // factorial(m) % (10 ** 9 + 7))