Watson asks Sherlock: 

Given a string S of N 0's and M 1's, how many unique permutations of this string start with 1?   

Help Sherlock by printing the answer modulo (10^{9}+7).   

Input Format 

First line contains T, the number of test cases. 

Each test case consists of N and M separated by a space.

Output Format 

For each test case, print the answer modulo (10^{9}+7).

Constraints 

1 ≤ T ≤ 200 

1 ≤ N,M ≤ 1000  

Sample Input   

2
1 1
2 3

Sample Output      

1
6

Explanation 

Test1: Out of all unique permutations ie. 01 and 10, only second permutation satisfies. Hence, output is 1. 

Test2: Out of all unique permutations ie. 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100, only 10011 10101 10110 11001 11010 11100 satisfy. Hence, output is 6.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
MOD = 1000000007
t = int(input())

def f(c0, c1):
	c1 -= 1
	res = 1
	for i in range(c0 + 1, c0 + c1 + 1):
		res = res * i // (i - c0)
	return res % MOD
for _ in range(t):
	(c0, c1) = map(int, input().split())
	print(f(c0, c1))


def ext_gcd(aneek, sayantan):
	ash = aneek // sayantan
	champa = aneek - sayantan * ash
	shreejit = [1, 0]
	while champa != 0:
		aneek = sayantan
		sayantan = champa
		shreejit.append(shreejit[0] - ash * shreejit[1])
		shreejit = shreejit[1:]
		ash = aneek // sayantan
		champa = aneek - sayantan * ash
	return shreejit[1]

def inv_mod(xavi, prime):
	barca = ext_gcd(xavi, prime)
	if barca < 0:
		barca += prime
	return barca

def comb(n, r, p):
	if r == 0 or n == r:
		return 1
	elif r == 1 or n == 1 + r:
		return n % p
	else:
		ans = 1
		r = min(r, n - r)
		for i in range(r):
			ans = ans * (n - i) % p
			ans = ans * inv_mod(i + 1, p) % p
		return ans
t = int(input())
p = int(1000000000.0 + 7)
for tst in range(t):
	s = input().strip().split()
	n = int(s[0])
	m = int(s[1])
	print(comb(m + n - 1, n, p))


T = int(input())
mod = 10 ** 9 + 7
F = [1, 1]

def nCr(n, r):
	ans = F[n]
	b = pow(F[r] * F[n - r], mod - 2, mod)
	ans *= b
	ans %= mod
	return ans
for i in range(2, 5003):
	F.append(F[-1] * i)
	F[-1] %= mod
for t in range(T):
	(N, M) = map(int, input().split())
	M -= 1
	print(nCr(N + M, N))


import math

def g(l):
	x = math.factorial(l[1] + l[0] - 1) // (math.factorial(l[0]) * math.factorial(l[1] - 1))
	return x % (10 ** 9 + 7)
t = int(input())
l = []
for i in range(t):
	s = str(input())
	s1 = s.split()
	for i in range(len(s1)):
		s1[i] = int(s1[i])
	l.append(g(s1))
for i in l:
	print(i)


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


from sys import stdin as cin
import math
f = [1, 1]
inf = [1, 1]
for i in range(2005):
	f.append((i + 2) * f[i + 1] % 1000000007)
	inf.append(pow(i + 2, 1000000005, 1000000007) * inf[i + 1] % 1000000007)

def nCr(n, r):
	return f[n] * inf[r] * inf[n - r] % 1000000007
for t in range(int(cin.readline())):
	(n, m) = map(int, cin.readline().split())
	print(nCr(n + m - 1, n))


t = int(input())
s = 1
while t > 0:
	s = 1
	f = 1
	(n, m) = map(int, input().split())
	for i in range(1, m):
		s = s * (n + i)
	for j in range(1, m):
		f = f * j
	print(s // f % 1000000007)
	t -= 1


import math
import sys
t = eval(input())
f = [1, 1]
inf = [1, 1]
for i in range(2005):
	f.append((i + 2) * f[i + 1] % 1000000007)
	inf.append(pow(i + 2, 1000000005, 1000000007) * inf[i + 1] % 1000000007)

def nCr(n, r):
	return f[n] * inf[r] * inf[n - r] % 1000000007
for i in range(0, t):
	(n, m) = map(int, input().split())
	print(int(nCr(n + m - 1, m - 1) % 1000000007))


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


MOD = 10 ** 9 + 7

def fact(n):
	v = 1
	while n > 0:
		v = v * n % MOD
		n -= 1
	return v

def gcde(a, b):
	(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
	while r2 > 0:
		q = r // r2
		(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
	return (r, u, v)

def invMod(a, m):
	(r, u, v) = gcde(a, m)
	if r != 1:
		return None
	return u
T = int(input())
for t in range(T):
	(N, M) = [int(_) for _ in input().split(' ')]
	print(fact(N + M - 1) * invMod(fact(N), MOD) * invMod(fact(M - 1), MOD) % MOD)


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


from math import factorial as f
for i in range(int(input())):
	(n, m) = [int(e) for e in input().split()]
	m -= 1
	print(f(n + m) // f(n) // f(m) % (10 ** 9 + 7))


test = int(input())
for f in range(test):
	u = input().split(' ')
	a = int(u[0])
	b = int(u[1])
	ans1 = 1
	for i in range(1, b):
		ans1 *= b + a - i
	ans2 = 1
	for i in range(1, b):
		ans2 *= i
	print(ans1 // ans2 % 1000000007)


def factorial(num):
	result = 1
	for i in range(1, num + 1):
		result *= i
	return result
t = int(input())
for asda in range(t):
	(zero, one) = list(map(int, input().split()))
	if one == 1:
		print(1)
		continue
	one = one - 1
	summed = one + zero
	print(int(factorial(summed) // (factorial(one) * factorial(summed - one))) % (10 ** 9 + 7))


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


import math

def modFact(x, start, m):
	product = 1
	for i in range(start, x + 1):
		product = product * i % m
	return product

def modInv(x, m):
	product = 1
	for i in range(m - 2):
		product = product * x % m
	return product

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 = int(math.pow(10, 9) + 7)
t = int(input())
for i in range(t):
	words = input().split()
	n = int(words[0])
	m = int(words[1])
	if m == 0:
		print('0')
		continue
	m -= 1
	ans = modFact(m + n, m + 1, p) * modinv(modFact(n, 1, p), p) % p
	print(ans)


from math import factorial

def CalculatePerm(zeros, ones):
	number = int(pow(10, 9) + 7)
	if ones == 0:
		return 0
	elif ones == 1:
		return 1
	else:
		ones -= 1
		return int(int(factorial(ones + zeros)) // int(factorial(ones) * factorial(zeros))) % number
T = int(input())
for i in range(T):
	inpStr = input()
	inpArray = inpStr.split()
	zeros = int(inpArray[0])
	ones = int(inpArray[1])
	print(CalculatePerm(zeros, ones))


from math import factorial as f

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


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


from math import factorial

def modexp(a, k, p):
	result = 1
	while k != 0:
		if k & 1 != 0:
			result = result * a % p
		k >>= 1
		a = a * a % p
	return result

def binomial(n, r, mod):
	result = 1
	for i in range(n, n - r, -1):
		result = result * i % mod
	denom = 1
	for i in range(1, r + 1):
		denom *= i
	result = result * modexp(denom, mod - 2, mod) % mod
	return result
T = int(input())
mod = pow(10, 9) + 7
for t in range(T):
	[N, M] = [int(x) for x in input().split()]
	print(binomial(N + M - 1, M - 1, mod))


from functools import reduce

def p(x):
	return reduce(lambda x, y: x * y, range(1, x + 1)) if x > 0 else 1
for ncase in range(int(input())):
	(N, M) = [int(i) for i in input().split(' ')]
	M -= 1
	print(p(M + N) // (p(M) * p(N)) % (10 ** 9 + 7))


def combine(a, b):
	(x, y) = (1, 1)
	for i in range(b):
		x *= a - i
		y *= i + 1
	return x // y % (10 ** 9 + 7)

def perm(m, n):
	return combine(m - 1 + n, n)
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(perm(m, n))


import math
cases = int(input())
for case in range(cases):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	MOD = 1000000007
	print(math.factorial(n + m - 1) // math.factorial(n) // math.factorial(m - 1) % MOD)


numCase = int(input())
for _ in range(numCase):
	(N, M) = map(int, input().split())
	if N == 0 or M == 0:
		print(1)
	else:
		den = 1
		nom = 1
		while N > 0:
			den *= N
			nom *= M + N - 1
			N -= 1
		print(nom // den % (10 ** 9 + 7))


mod = 10 ** 9 + 7

def fact(n):
	if n == 0:
		return 1
	result = 1
	for i in range(1, n + 1):
		result *= i
	return result
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	m -= 1
	result = fact(m + n) // (fact(n) * fact(m)) % mod
	print(result)


def bincoeff(n, k):
	if 0 <= k <= n:
		n2k = 1
		k2k = 1
		for i in range(1, min(k, n - k) + 1):
			n2k *= n
			k2k *= i
			n -= 1
		return n2k // k2k
	else:
		return 0
for t in range(int(input())):
	(n, m) = str(input()).split()
	(n, m) = (int(n), int(m))
	result = bincoeff(n + m - 1, n) % 1000000007
	print(result)


def modPow(a, x, p):
	res = 1
	while x > 0:
		if x % 2 != 0:
			res = res * a % p
		a = a * a % p
		x //= 2
	return res

def modInverse(a, p):
	return modPow(a, p - 2, p)

def modBinomial(n, k, p):
	numerator = 1
	for i in range(0, k):
		numerator = numerator * (n - i) % p
	denominator = 1
	for i in range(1, k + 1):
		denominator = denominator * i % p
	return numerator * modInverse(denominator, p) % p
import sys
n = int(sys.stdin.readline())
for i in range(0, n):
	(N, M) = map(int, sys.stdin.readline().split(' '))
	print(modBinomial(N + M - 1, N, 10 ** 9 + 7))


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


import math
t = int(input())
while t > 0:
	t -= 1
	numbers = []
	numbers = input().split()
	numbers = [int(x) for x in numbers]
	(zeros, ones) = (numbers[0], numbers[1])
	ones -= 1
	total = zeros + ones
	factTotal = math.factorial(total)
	factOnes = math.factorial(ones)
	factZeros = math.factorial(zeros)
	ans = factTotal // (factOnes * factZeros)
	ans = ans % 1000000007
	print(ans)


import math
t = int(input().strip())
f = math.factorial
while t:
	(n, m) = map(int, input().strip().split())
	print(f(n + m - 1) // (f(n) * f(m - 1)) % 1000000007)
	t -= 1


t = int(input())
dp = [-1 for i in range(2001)]
dp[0] = 1
dp[1] = 1

def fact(n):
	if dp[n] != -1:
		return dp[n]
for j in range(2, 2001):
	dp[j] = dp[j - 1] * j
for i in range(t):
	a = [int(x) for x in input().split()]
	fact0 = fact(a[0])
	fact1 = fact(a[1] - 1)
	mainfact = fact(a[0] + (a[1] - 1))
	total = int(int(mainfact // (fact0 * fact1)) % (10 ** 9 + 7))
	print(total)


import math
T = int(input())
for i in range(T):
	nums = list(map(int, input().split()))
	nums[1] -= 1
	ans = math.factorial(nums[0] + nums[1]) // (math.factorial(nums[0]) * math.factorial(nums[1])) % (10 ** 9 + 7)
	print(ans)


Matrix = [[0 for x in range(0, 1001)] for x in range(0, 2001)]
for i in range(1, 2001):
	Matrix[i][0] = 1
	Matrix[i][min(i, 1000)] = 1
	for j in range(1, min(1001, i)):
		Matrix[i][j] = (Matrix[i - 1][j] + Matrix[i - 1][j - 1]) % 1000000007
t = int(input())
while t > 0:
	str_arr = input().split()
	arr = [int(num) for num in str_arr]
	print(Matrix[arr[0] + arr[1] - 1][arr[1] - 1])
	t = t - 1


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


def modpow(a, x, p):
	res = 1
	while x > 0:
		if x % 2 != 0:
			res = res * a % p
		a = a * a % p
		x = x >> 1
	return res

def modInverse(a, p):
	return modpow(a, p - 2, p)

def modBinomial(n, k, p):
	numerator = 1
	i = 0
	while i < k:
		numerator = numerator * (n - i) % p
		i = i + 1
	denominator = 1
	i = 1
	while i <= k:
		denominator = denominator * i % p
		i = i + 1
	res = modInverse(denominator, p)
	res = res * numerator % p
	return res
t = int(input())
while t > 0:
	str = input()
	l = str.split()
	n = int(l[0])
	m = int(l[1]) - 1
	if m > n:
		temp = m
		m = n
		n = temp
	ans = modBinomial(n + m, m, 1000000007)
	print(ans % 1000000007)
	t = t - 1


C = [[1 for _ in range(2001)] for _ in range(2001)]
for i in range(2001):
	for j in range(1, i):
		C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(C[n + m - 1][n])


grid = [None] * 1001
for i in range(1001):
	grid[i] = [None] * 1001
for i in range(1001):
	for j in range(1001):
		if i == 0 or j == 0:
			grid[i][j] = 1
		else:
			grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
T = int(input())
for i in range(T):
	imp = input().strip().split()
	n = int(imp[0])
	m = int(imp[1]) - 1
	print(grid[n][m] % 1000000007)


def fact_mod(n, mod):
	x = 1
	for i in range(1, n + 1):
		x = x * (i % mod)
	return x % mod

def pow_mod(base, exp, mod):
	result = 1
	base = base % mod
	while exp:
		if exp & 1:
			result = result * base % mod
		exp >>= 1
		base = base * base % mod
	return result
mod = pow(10, 9) + 7
T = int(input())
for t in range(T):
	[N, M] = list(map(int, input().split()))
	Num = fact_mod(N + M - 1, mod)
	t1 = fact_mod(N, mod)
	t2 = fact_mod(M - 1, mod)
	Den = pow_mod(t1 * t2, mod - 2, mod)
	print(Num * Den % mod)


from math import factorial
numCases = int(input())
for _ in range(numCases):
	(n, m) = [int(n) for n in input().split(' ')]
	if m == 0:
		print(0)
	else:
		print(int(factorial(n + m - 1) // (factorial(n) * factorial(m - 1)) % 1000000007))


import math, sys
MODULUS = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MODULUS)


MOD = 10 ** 9 + 7

def main():
	ncases = int(input())
	for case in range(ncases):
		(n, m) = list(map(int, input().split()))
		print(comb(m + n - 1, n))

def comb(n, m):
	num = den = 1
	if m + m > n:
		m = n - m
	for i in range(m):
		num = num * (n - i) % MOD
		den = den * (i + 1) % MOD
	return num * pow(den, MOD - 2, MOD) % MOD
main()


P = 10 ** 9 + 7

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

def mult_inv(a, m):
	return egcd(m, a)[2] % m

def choose(n, k):
	import functools
	if k + 1 < n + 1:
		numerator = functools.reduce(lambda x, y: x * y % P, range(k + 1, n + 1))
	else:
		numerator = 1
	if 1 < n - k + 1:
		denominator = functools.reduce(lambda x, y: x * y % P, range(1, n - k + 1))
	else:
		denominator = 1
	return mult_inv(denominator, P) * numerator % P
T = int(input())
for i in range(T):
	(N, M) = tuple(map(int, input().split(' ')))
	print(choose(M - 1 + N, max(N, M - 1)))


def ifact(n):
	fact = 1
	for i in range(1, n + 1, 1):
		fact *= i
	return int(fact)

def nCr(n, r):
	comb = ifact(n) // (ifact(r) * ifact(n - r))
	return int(comb)
mod = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	[z, o] = [int(i) for i in input().split()]
	print(nCr(z + o - 1, z) % mod)


import math
numTests = int(input())
for n in range(0, numTests):
	inputs = [int(i) for i in input().split()]
	px = math.factorial(inputs[0] + (inputs[1] - 1))
	dx = math.factorial(inputs[0]) * math.factorial(inputs[1] - 1)
	print(px // dx % (pow(10, 9) + 7))


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


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


import math
t = int(input())
for _ in range(t):
	(z, o) = [int(x) for x in input().split()]
	o -= 1
	ans = math.factorial(z + o) // (math.factorial(z) * math.factorial(o)) % (10 ** 9 + 7)
	print(ans)


import math
from collections import namedtuple
case_count = int(input())
Case = namedtuple('Case', ['n', 'm'])
cases = [Case._make((int(i) for i in input().split())) for _ in range(case_count)]

def combination(n, k):
	return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
for case in cases:
	print(combination(case.n + (case.m - 1), case.m - 1) % (10 ** 9 + 7))


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

def choose(a, b):
	print(factorial(a) // (factorial(b) * factorial(a - b)) % M)
t = int(input())
for i in range(0, t):
	args = [int(a) for a in input().split()]
	choose(args[0] + args[1] - 1, args[0])


def fact(a, P):
	op = 1
	for I in range(2, a + 1):
		op = op * I % P
	return op

def fast_power(a, b, P):
	if b == 0:
		return 1
	if b == 1:
		return a % P
	if b % 2 == 0:
		intermed = fast_power(a, b / 2, P)
		return intermed ** 2 % P
	else:
		intermed = fast_power(a, b - 1, P)
		return intermed * a % P
t = int(input().strip())
P = 10 ** 9 + 7
for _ in range(t):
	(n, m) = [int(x) for x in input().strip().split(' ')]
	Nr = fact(n + m - 1, P)
	Dr = fast_power(fact(n, P), P - 2, P) * fast_power(fact(m - 1, P), P - 2, P) % P
	op = Nr * Dr % P
	print(op)


import sys
import math

def unique_permutations(nzeros, nones):
	npermutations = math.factorial(nzeros + nones)
	nzeros_factorial = math.factorial(nzeros)
	nones_factorial = math.factorial(nones)
	return npermutations // nzeros_factorial // nones_factorial

def unique_permutations_starting_with_one(nzeros, nones):
	return unique_permutations(nzeros, nones - 1)
ncases = int(sys.stdin.readline())
for case_index in range(ncases):
	(nzeros, nones) = [int(x) for x in sys.stdin.readline().split()]
	print(unique_permutations_starting_with_one(nzeros, nones) % int(1000000000.0 + 7))


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


import math
const = 1000000007
t = int(input())
for i in range(t):
	(n, m) = tuple(map(int, input().split(' ')))
	m -= 1
	p = m + n
	ans = math.factorial(p) // (math.factorial(n) * math.factorial(m))
	ans = ans % const
	print(ans)


import sys
source = sys.stdin
modulus = 10 ** 9 + 7
T = int(source.readline())
for _ in range(T):
	(N, M) = tuple([int(s) for s in source.readline().split()])
	if M == 0:
		print(0)
	else:
		A = max(N, M - 1)
		B = min(N, M - 1)
		k = B
		result = 1
		for j in range(A + B, A, -1):
			result *= j
			while k > 1 and result % k == 0:
				result = result // k
				k -= 1
			if k == 1:
				result = result % modulus
		result = result % modulus
		print(result)


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


T = int(input())
p = 10 ** 9 + 7
a = b = 1000
matrix = [[1 for x in range(a + 1)] for x in range(b + 1)]
for i in range(1, a + 1):
	for j in range(1, b + 1):
		matrix[i][j] = (matrix[i - 1][j] + matrix[i][j - 1]) % p
for t in range(T):
	(n, m) = input().strip().split(' ')
	(n, m) = (int(n), int(m))
	print(matrix[n][m - 1])


import math
n = int(input())
while n:
	(N, M) = map(int, input().split())
	ans = math.factorial(N + M - 1) // (math.factorial(N) * math.factorial(M - 1))
	print(ans % 1000000007)
	n -= 1


def count(a, b):
	c = 1
	toDivide = 1
	for i in range(a + 1, a + b + 1):
		c *= i
	for i in range(1, b + 1):
		toDivide *= i
	return int(c // toDivide % (10 ** 9 + 7))
n = int(input())
for i in range(0, n):
	(a, b) = input().split(' ')
	(a, b) = (int(a), int(b))
	print(count(a, b - 1))


def choose(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
T = int(input())
mod = 10 ** 9 + 7
for _ in range(T):
	(N, M) = map(int, input().split())
	total = M + N
	print(int(choose(total - 1, M - 1)) % mod)


size = 2000
comb = [[0] * size for _ in range(size)]
for i in range(size):
	comb[i][0] = 1
for y in range(1, size):
	for x in range(1, size):
		comb[y][x] = comb[y - 1][x - 1] + comb[y - 1][x]

def ncr(n, k):
	assert n < size
	return comb[n][k]
T = int(input())
for case in range(T):
	(N, M) = map(int, input().split(' '))
	print(ncr(N + M - 1, N) % (10 ** 9 + 7))


from math import factorial

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))
numTests = int(input())
for test in range(numTests):
	(numZeros, numOnes) = [int(num) for num in input().split(' ')]
	if numOnes == 0:
		print('0')
	else:
		print(ncr(numOnes + numZeros - 1, numZeros) % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	M -= 1
	N += M
	result = 1
	for i in range(1, M + 1):
		result = result * (N - i + 1) // i
	print(result % MOD)


mod = 10 ** 9 + 7
t = int(input())
cases = []
for _ in range(t):
	(n, m) = map(int, input().split())
	cases.append((n, m))
nmmax = max((n + m for (n, m) in cases))
rs = [[1]]
for i in range(nmmax - 1):
	rs.append([1] + [(rs[-1][j] + rs[-1][j + 1]) % mod for j in range(i)] + [1])
for (n, m) in cases:
	print(rs[n + m - 1][m - 1])


import math

def arrangements(n, m):
	a = math.factorial(n + m)
	b = math.factorial(n) * math.factorial(m)
	return a // b
tests = int(input())
for test in range(tests):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	print(arrangements(n, m - 1) % (10 ** 9 + 7))


matr = [[0 for i in range(2001)] for j in range(2001)]
for i in range(0, 2001):
	matr[0][i] = matr[i][i] = 1
for i in range(2, 2001):
	for j in range(1, i):
		matr[i][j] = (matr[i - 1][j - 1] + matr[i - 1][j]) % 1000000007
t = int(input())
for k in range(0, t):
	x = input().split()
	a = int(x[0])
	b = int(x[1])
	print(matr[a + b][a + 1])


def readintlist():
	l = input().split()
	for i in range(len(l)):
		l[i] = int(l[i])
	return l

def factorial(n):
	product = 1
	for i in range(2, n + 1):
		product *= i
	return product
T = int(input())
for tc in range(T):
	nm = readintlist()
	n = nm[0]
	m = nm[1]
	print(factorial(n + m - 1) // factorial(n) // factorial(m - 1) % 1000000007)


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


T = int(input())

def c(n, k):
	res = 1
	for x in range(k + 1, n + 1):
		res *= x
	for x in range(1, n - k + 1):
		res = res // x
	return res % 1000000007
for t in range(T):
	(n, m) = (int(x) for x in input().split())
	print(c(n + m - 1, n))


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


import math
T = int(input())
for _ in range(T):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % 1000000007)


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


fact = [0 for n in range(2010)]
fact[0] = 1
fact[1] = 1
fact[2] = 2
fact[3] = 6
for i in range(4, 2001):
	fact[i] = fact[i - 1] * i
t = int(input())
while t > 0:
	inz = input().split()
	n = int(inz[0])
	m = int(inz[1])
	m -= 1
	print(fact[n + m] // (fact[n] * fact[m]) % 1000000007)
	t -= 1


def binomial_coeff(n, k):
	if k <= 0 or k >= n:
		return 1
	else:
		k = min(k, n - k)
		res = 1
		div = 1
		while k > 0:
			res *= n
			div *= k
			k -= 1
			n -= 1
		return res // div % (10 ** 9 + 7)

def main():
	t = int(input())
	for x in range(t):
		(n, m) = map(int, input().split())
		print(binomial_coeff(n + m - 1, n))
main()


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


comb = {}
for i in range(2001):
	comb[i, 0] = 1
	comb[i, i] = 1
	for j in range(1, i):
		comb[i, j] = (comb[i - 1, j] + comb[i - 1, j - 1]) % 1000000007
numTrials = int(input())
for i in range(numTrials):
	L = input().split()
	(N, M) = (int(L[0]), int(L[1]))
	print(comb[N + M - 1, N])


import math
n = int(input())
for i in range(n):
	(x, y) = tuple(map(int, input().split()))
	res = math.factorial(x + y - 1)
	res = res // (math.factorial(x) * math.factorial(y - 1))
	print(res % 1000000007)


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

def nCk(n, k):
	return int(reduce(mul, (Fraction(n - i, i + 1) for i in range(k)), 1))
S = int(input())
for _ in range(S):
	(N, M) = [int(x) for x in input().split()]
	print(nCk(N + M - 1, N) % 1000000007)


from itertools import repeat

def ncr(n):
	c = [list(repeat(0, i + 1)) for i in range(n + 1)]
	for i in range(n + 1):
		(c[i][0], c[i][i]) = (1, 1)
	for i in range(2, n + 1):
		for j in range(1, i):
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 1000000007
	return c
t = int(input())
a = []
mm = 0
for k in range(t):
	x = [int(i) for i in input().split(' ')]
	if sum(x) > mm:
		mm = sum(x)
	a.append(x)
c = ncr(mm)
for (n, m) in a:
	m = m - 1
	print(c[n + m][m])


def pascal(n):
	x = [[1] * (i + 1) for i in range(n + 1)]
	for r in range(2, n + 1):
		for c in range(1, r):
			x[r][c] = (x[r - 1][c - 1] + x[r - 1][c]) % 1000000007
	return x
t = int(input())
max = 0
cases = []
for j in range(t):
	c = [int(i) for i in input().split(' ')]
	sum = 0
	for i in c:
		sum += i
	if sum - 1 > max:
		max = sum - 1
	cases.append(c)
tri = pascal(max)
for i in cases:
	n = i[0]
	m = i[1]
	val = tri[n + m - 1][m - 1]
	print(val)


MOD = pow(10, 9) + 7

def pascal_triangle(n, p):
	pascal = [x[:] for x in [[0] * (n + 1)] * (n + 1)]
	pascal[0][0] = 1
	for i in range(1, n + 1):
		pascal[i][0] = 1
		for j in range(1, i + 1):
			pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][j - 1]) % p
	return pascal
biggest_n = 0
q = []
for T in range(int(input().strip())):
	(N, M) = [int(x) for x in input().strip().split()]
	N += M - 1
	M -= 1
	q.append((N, M))
	if N > biggest_n:
		biggest_n = N
pascal = pascal_triangle(biggest_n, MOD)
for t in q:
	print(pascal[t[0]][t[1]])


t = int(input())
MODULO = 1000000007

def PowMod(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = x * a % MODULO
		a = a * a % MODULO
		n >>= 1
	return x % MODULO
fact = [1, 1]
for i in range(2, 2001):
	fact.append(i * fact[i - 1] % MODULO)
for i in range(t):
	(n, m) = list(map(int, input().split()))
	ans = fact[n + m - 1] * PowMod(fact[m - 1] * fact[n] % MODULO, MODULO - 2)
	print(ans % MODULO)


import math
T = int(input())
for t in range(T):
	line = input()
	N = int(line.split(' ')[0])
	M = int(line.split(' ')[1])
	M -= 1
	print(math.factorial(N + M) // (math.factorial(N) * math.factorial(M)) % (10 ** 9 + 7))


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


from math import factorial
t = int(input())
for i in range(t):
	(zeros, ones) = (int(x) for x in input().split(' '))
	ones = ones - 1
	tot = zeros + ones
	totperm = factorial(tot) // (factorial(zeros) * factorial(ones))
	print(totperm % (10 ** 9 + 7))


from functools import reduce
import operator as op
from math import factorial
t = int(input())
tests = []
for i in range(t):
	tests.append(tuple(input().split()))

def nCk(n, k):
	k = min(k, n - k)
	if k < 0:
		return 0
	if k == 0:
		return 1
	return reduce(op.mul, range(n - k + 1, n + 1), 1) // factorial(k)
mod = int(1000000000.0 + 7)
for test in tests:
	n = int(test[0])
	m = int(test[1])
	print(nCk(n + m - 1, m - 1) % mod)


t = input()
t = int(t)

def fakulteta(n):
	if n == 1 or n == 0:
		return 1
	else:
		vrni = 1
		while n > 1:
			vrni *= n
			n = n - 1
		return vrni

def kombinacije(n, r):
	return fakulteta(n) // fakulteta(r) // fakulteta(n - r)
for i in range(t):
	x = input()
	(a, b) = x.split(' ')
	(a, b) = (int(a), int(b))
	print(kombinacije(a + b - 1, a) % (10 ** 9 + 7))


from math import factorial
T = int(input())

def mod_fact(n, p):
	out = 1
	for i in range(1, n + 1):
		out = int(out * i) % p
	return out

def mod_exp(a, b, p):
	r = 0
	if b == 0:
		return 1
	elif b % 2 == 0:
		return mod_exp(a, b / 2, p) ** 2 % p
	else:
		return a * mod_exp(a, b - 1, p) % p
for t in range(0, T):
	(n, m) = [int(x) for x in input().split()]
	p = 1000000007
	if m != 1:
		num = mod_fact(n + m - 1, p) % p
		den = mod_fact(n, p) % p * mod_fact(m - 1, p) % p % p
		den = mod_exp(den, p - 2, p)
		print(num * den % p)
	else:
		print(1)


from math import factorial as f
testcases = int(input().strip())
mmod = 10 ** 9 + 7

def binom(a, b):
	return f(a) // (f(b) * f(a - b))
for _ in range(testcases):
	(n, m) = [int(x) for x in input().strip().split()]
	if n == 0:
		print(0)
	else:
		print(binom(n + m - 1, n) % mmod)


from math import factorial
cases = int(input())
for i in range(cases):
	(N, M) = list(map(int, input().split()))
	res = factorial(N + M - 1) // factorial(N) // factorial(M - 1)
	res = res % (10 ** 9 + 7)
	print(res)


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


from math import factorial

def nCr(n, r):
	return factorial(n) // factorial(r) // factorial(n - r)
for _ in range(int(input())):
	(zeros, ones) = map(int, input().split())
	print(nCr(zeros + ones - 1, zeros) % 1000000007)


import math, sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print(math.factorial(N + M - 1) // math.factorial(N) // math.factorial(M - 1) % MOD)


from math import factorial
d = 10 ** 9 + 7
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	if M == 0:
		print('0')
	else:
		m = M - 1
		print(factorial(m + N) // (factorial(N) * factorial(m)) % d)


from math import factorial

def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(N, M) = [int(ns) for ns in str(input()).split()]
	if M == 1:
		print(1)
		continue
	if N == 1:
		print(M)
		continue
	M -= 1
	a = M + N
	print(int(factorial(a)) % mod * modinv(int(factorial(M) * factorial(N)), mod) % mod)


modulo = 10 ** 9 + 7

def Comb(n, tmp):
	r = tmp
	if n - tmp < r:
		r = n - tmp
	if r == 0:
		return 1
	num = 1
	den = 1
	for cnt in range(r):
		num *= n - cnt
		den *= cnt + 1
	cmb = int(num % (den * modulo) / den)
	return cmb
T = int(input())
for tmp in range(T):
	[N, M] = list(map(int, input().strip().split(' ')))
	print(Comb(M + N - 1, N))


from math import factorial

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

def perm(n, m):
	result = nCk(n + m - 1, n)
	k = 10 ** 9 + 7
	return result % k

def main():
	t = int(input())
	for i in range(0, t):
		ar = input().split()
		n = int(ar[0])
		m = int(ar[1])
		print(perm(n, m))
main()


from math import factorial as f
T = int(input())
modulo = 1000000007
for _ in range(T):
	(N, M) = map(int, input().split())
	M -= 1
	x = f(N + M) // (f(N) * f(M))
	print(x % modulo)


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