A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"

MATHE  
ATHEM  
THEMA  
HEMAT  
EMATI  
MATIC  
ATICS  

There are many ways to trace this matrix in a way that helps you construct this word. You start tracing the matrix from the top-left position and at each iteration, you either move RIGHT or DOWN, and ultimately reach the bottom-right of the matrix. It is assured that any such tracing generates the same word. How many such tracings can be possible for a given
word of length m+n-1 written as a matrix of size m * n?

Input Format 

The first line of input contains an integer T. T test cases follow. 

Each test case contains 2 space separated integers m & n (in a new line) indicating that the matrix has m rows and each row has n characters.  

Constraints 

1 <= T <= 10^{3} 

1 ≤ m,n ≤ 10^{6}

Output Format 

Print the number of ways (S) the word can be traced as explained in the problem statement.
If the number is larger than 10^{9}+7, 

print  S mod (10^9 + 7) for each testcase (in a new line). 

Sample Input

1
2 3

Sample Output

3

Explanation 

Let's consider a word AWAY written as the matrix

AWA
WAY

Here, the word AWAY can be traced in 3 different ways, traversing either RIGHT or DOWN.

AWA
  Y

AW
 AY

A
WAY

Hence the answer is 3.

Timelimit
Time limit for this challenge is given here

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Mathematics


Solutions:
import sys

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, 1000000007))


import math

def fact(n, p):
	prod = 1
	if n >= p:
		return 0
	for i in range(1, n + 1):
		prod = prod * i % p
	return prod

def solve(m, n):
	x = fact(m + n - 2, 1000000007)
	y = pow(fact(m - 1, 1000000007) * fact(n - 1, 1000000007), 1000000005, 1000000007)
	return x * y % 1000000007
T = int(input())
for i in range(0, T):
	nums = input()
	(m, n) = nums.split()
	m = int(m)
	n = int(n)
	print(solve(m, n))


from sys import stdin
fact = {0: 1}
f = 1
for i in range(1, 2 * 10 ** 6 + 1):
	f = f * i % (10 ** 9 + 7)
	fact[i] = f

def factorial(n):
	return fact[n]

def invfactorial(n):
	return pow(fact[n], 10 ** 9 + 7 - 2, 10 ** 9 + 7)

def binomial(m, n):
	return factorial(m) * invfactorial(n) * invfactorial(m - n) % (10 ** 9 + 7)
T = int(stdin.readline())
for _ in range(T):
	(m, n) = (int(s) for s in stdin.readline().strip().split())
	print(binomial(m + n - 2, n - 1))


import sys
raw_data = [i.strip() for i in sys.stdin.readlines()[1:]]
modulus = 10 ** 9 + 7
fac_values = [1]
for i in range(1, 2000001):
	fac_values.append(fac_values[-1] * i % modulus)

def _extended_euclidian(a, b):
	if b == 0:
		return [a, 1, 0]
	else:
		m = _extended_euclidian(b, a % b)
		return [m[0], m[2], m[1] - a // b * m[2]]

def extended_euclidian(a, b):
	if a < b:
		m = _extended_euclidian(b, a)
		return [m[0], m[2], m[1]]
	return _extended_euclidian(a, b)

def inverse(n, p):
	return extended_euclidian(n, p)[1]

def binom(n, k):
	a = inverse(fac_values[k], modulus)
	b = inverse(fac_values[n - k], modulus)
	return a * b * fac_values[n] % modulus

def get_answer(list_of_nums):
	m = list_of_nums[0]
	n = list_of_nums[1]
	return binom(m + n - 2, m - 1)
for x in raw_data:
	print(get_answer([int(i) for i in x.split()]))


from sys import stdin

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

def nCr(n, r):
	fact_n_r = 1
	for i in range(n - r + 1, n + 1):
		fact_n_r *= i
		fact_n_r %= 1000000007
	fact_r = 1
	for i in range(1, r + 1):
		fact_r *= i
		fact_r %= 1000000007
	return fact_n_r * modinv(fact_r, 1000000007) % 1000000007
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	(m, n) = map(int, inpu[i].split())
	print(nCr(n + m - 2, n - 1))


MODULO = 10 ** 9 + 7
LIMIT = 10 ** 6
FACTORIALS = [1]

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:
		return None
	else:
		return x % m

def precompute_factorials():
	for i in range(1, LIMIT * 2):
		FACTORIALS.append(FACTORIALS[i - 1] * i % MODULO)

def matrix_tracing(m, n):
	numerator = FACTORIALS[m + n - 2]
	denominator = FACTORIALS[m - 1] * FACTORIALS[n - 1] % MODULO
	return numerator * modinv(denominator, MODULO) % MODULO

def main():
	test_num = int(input())
	precompute_factorials()
	for i in range(test_num):
		line = input()
		(m, n) = [int(x) for x in line.split()]
		print(matrix_tracing(m, n))
main()


from sys import stdin

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

def nCr(n, r):
	fact_n_r = 1
	for i in range(n - r + 1, n + 1):
		fact_n_r *= i
		fact_n_r %= 1000000007
	fact_r = 1
	for i in range(1, r + 1):
		fact_r *= i
		fact_r %= 1000000007
	return fact_n_r * modinv(fact_r, 1000000007) % 1000000007
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	(m, n) = map(int, inpu[i].split())
	print(nCr(n + m - 2, n - 1))


from sys import stdin

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

def nCr(n, r):
	fact_n_r = 1
	for i in range(n - r + 1, n + 1):
		fact_n_r *= i
		fact_n_r %= 1000000007
	fact_r = 1
	for i in range(1, r + 1):
		fact_r *= i
		fact_r %= 1000000007
	return fact_n_r * modinv(fact_r, 1000000007) % 1000000007
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	(m, n) = map(int, inpu[i].split())
	print(nCr(n + m - 2, n - 1))


import math
import sys

def ncr(n, r):
	c = 1
	if r == 0:
		return 1
	if r > n - r:
		r = n - r
	for i in range(1, r + 1):
		c = c * (n - i + 1) // i
	return c

def ncr2(n, r, m):
	if r == 0:
		return 1
	if r > n - r:
		r = n - r
	f1 = 1
	f2 = 1
	for i in range(r):
		f1 = (n - i) * f1 % m
		f2 = (i + 1) * f2 % m
	c = f1 * pow(f2, m - 2, m) % m
	return c
T = int(input())
while T > 0:
	S = input()
	l = S.split()
	M = int(l[0])
	N = int(l[1])
	S = int(ncr2(M + N - 2, M - 1, 1000000007))
	print(S)
	T = T - 1


import math
p = 1000000007

def inverse(a):
	b = p - 2
	c = a
	a = 1
	while b > 0:
		if b % 2 == 1:
			a = a * c
			if a > p:
				a = a % p
		c = c * c
		if c > p:
			c = c % p
		b = int(b / 2)
	return a

def fact(n):
	i = 1
	j = 1
	while i <= n:
		j = j * i % p
		i = i + 1
	j = j % p
	return j
t = int(input())
while t > 0:
	(f, g) = map(int, input().split())
	f = f - 1
	g = g - 1
	h = f + g
	f = fact(f)
	g = fact(g)
	x = inverse(f)
	y = inverse(g)
	z = fact(h)
	ans = x
	ans = x * y
	ans = ans % p
	ans = ans * z
	ans = ans % p
	print(ans)
	t = t - 1


import sys
import itertools
import math
MOD = 1000000007
inp = [(int(x.split()[0]), int(x.split()[1])) for x in sys.stdin.read().split('\n')[1:] if x.strip() != '']
for (x, y) in inp:
	N = x + y - 2
	M = x - 1
	a = b = 1
	for i in range(x, x + y - 1):
		a *= i
		b *= i - x + 1
		a = a if a < MOD else a % MOD
		b = b if b < MOD else b % MOD
	b = pow(b, MOD - 2, MOD)
	print(a * b % MOD)


mod = 10 ** 9 + 7

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	if r > n:
		return 0
	nu = 1
	for i in range(n - r + 1, n + 1):
		nu = nu * i % p
	de = 1
	for i in range(2, r + 1):
		de = de * i % p
	return nu * modinv(de, p) % p
for case in range(int(input())):
	(m, n) = map(int, input().split())
	print(ncr(m + n - 2, n - 1, mod))


MODULO = 10 ** 9 + 7
LIMIT = 10 ** 6
FACTORIALS = [1]

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:
		return None
	else:
		return x % m

def precompute_factorials():
	for i in range(1, LIMIT * 2):
		FACTORIALS.append(FACTORIALS[i - 1] * i % MODULO)

def matrix_tracing(m, n):
	numerator = FACTORIALS[m + n - 2]
	denominator = FACTORIALS[m - 1] * FACTORIALS[n - 1] % MODULO
	return numerator * modinv(denominator, MODULO) % MODULO

def main():
	test_num = int(input())
	precompute_factorials()
	for i in range(test_num):
		line = input()
		(m, n) = [int(x) for x in line.split()]
		print(matrix_tracing(m, n))
main()


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):
	(x, y) = list(map(int, sys.stdin.readline().split(' ')))
	print(modBinomial(x + y - 2, y - 1, 10 ** 9 + 7))


M = 1000000007
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	num = den = 1
	for i in range(1, m + n - 1):
		num = num % M * (i % M) % M
	for i in range(1, m):
		den = den % M * (i % M) % M
	for i in range(1, n):
		den = den % M * (i % M) % M
	print(num % M * (pow(den, M - 2, M) % M) % M)


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


MODULO = 10 ** 9 + 7
LIMIT = 10 ** 6
FACTORIALS = [1]

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:
		return None
	else:
		return x % m

def precompute_factorials():
	for i in range(1, LIMIT * 2):
		FACTORIALS.append(FACTORIALS[i - 1] * i % MODULO)

def matrix_tracing(m, n):
	numerator = FACTORIALS[m + n - 2]
	denominator = FACTORIALS[m - 1] * FACTORIALS[n - 1] % MODULO
	return numerator * modinv(denominator, MODULO) % MODULO

def main():
	test_num = int(input())
	precompute_factorials()
	for i in range(test_num):
		line = input()
		(m, n) = [int(x) for x in line.split()]
		print(matrix_tracing(m, n))
main()


import math

def modinv(a, p):
	return pow(a, p - 2, p)

def binomial(n, r, p):
	if r > n // 2:
		return binomial(n, n - r, p)
	numerator = 1
	for i in range(n - r + 1, n + 1):
		numerator *= i
		numerator %= p
	denominator = 1
	for i in range(1, r + 1):
		denominator *= i
		denominator %= p
	return modinv(denominator, p) * numerator % p
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	mod = 10 ** 9 + 7
	print(binomial(m + n - 2, m - 1, mod))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


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

def binomialCoeff(n, k):
	if k == 0:
		return 1
	elif k > n // 2:
		return binomialCoeff(n, n - k)
	else:
		num = 1
		den = 1
		for p in range(k):
			num *= n - p
			num %= 10 ** 9 + 7
			den *= k - p
			den %= 10 ** 9 + 7
		den = modinv(den, 10 ** 9 + 7)
		return num * den % (10 ** 9 + 7)

def main():
	t = int(input())
	for _ in range(t):
		(m, n) = list(map(int, input().split()))
		print(binomialCoeff(m + n - 2, n - 1))
main()


from functools import reduce

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

def factorial_mod(n, prime):
	if n == 0:
		return 1
	else:
		return reduce(lambda a, b: a * b % prime, range(1, n + 1))

def choose_mod(n, k, p):
	return factorial_mod(n, p) * pow(factorial_mod(k, p) * factorial_mod(n - k, p), p - 2, p) % p
prime = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(m, n) = inpt()
	print(choose_mod(m + n - 2, m - 1, prime))


def choose(n, k, p):
	ways = 1
	sieve = [True] * (n + 1)
	for i in range(2, n + 1):
		if sieve[i]:
			for j in range(i * i, n + 1, i):
				sieve[j] = False
			d = i
			while d <= n:
				count = n // d - k // d - (n - k) // d
				for j in range(count):
					ways *= i
					ways %= p
				d *= i
	return ways
T = int(input())
for t in range(T):
	(m, n) = map(int, input().split())
	if n > m:
		(m, n) = (n, m)
	p = 10 ** 9 + 7
	print(choose(m + n - 2, n - 1, p))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


from math import factorial

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
T = int(input())
for t in range(0, T):
	(m, n) = [int(x) for x in input().split()]
	p = 1000000007
	num = mod_fact(m + n - 2, p)
	den = mod_fact(m - 1, p) * mod_fact(n - 1, p) % p
	den = mod_exp(den, p - 2, p)
	print(num * den % p)


from math import factorial

def factorialMod(n, modulus):
	ans = 1
	if n <= modulus // 2:
		for i in range(1, n + 1):
			ans = ans * i % modulus
	else:
		for i in range(n + 1, modulus):
			ans = ans * i % modulus
		ans = modinv(ans, modulus)
		ans = -1 * ans + modulus
	return ans % modulus
size = int(input())
modv = 10 ** 9 + 7
for i in range(size):
	(m, n) = map(int, input().split())
	tmp = factorialMod(m - 1, modv) * factorialMod(n - 1, modv)
	v2 = pow(tmp, modv - 2, modv)
	v1 = factorialMod(n + m - 2, modv)
	res = v1 * v2 % modv
	print('%d' % res)


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


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

def modBinomial(n, k, p):
	numerator = 1
	for i in range(k):
		numerator = numerator * (n - i) % p
	denominator = 1
	for i in range(1, k + 1):
		denominator = denominator * i % p
	return numerator * modinv(denominator, p) % p
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(1)
		continue
	M -= 1
	N -= 1
	print(modBinomial(M + N, M, mod))


mod_inverse_cache = {}

def mod_inverse(a, n):
	if a not in mod_inverse_cache:
		(t, newt) = (0, 1)
		(r, newr) = (n, a)
		while newr:
			q = r // newr
			(t, newt) = (newt, t - q * newt)
			(r, newr) = (newr, r - q * newr)
		if r > 1:
			return None
		mod_inverse_cache[a] = t if t >= 0 else t + n
	return mod_inverse_cache[a]

def mod_ncr(n, k, r):
	k = min(k, n - k)
	res = 1
	for i in range(k):
		res = res * (n - i) * mod_inverse(i + 1, r) % r
	return res
r = 10 ** 9 + 7
n_tests = int(input())
for t in range(n_tests):
	(m, n) = map(int, input().split())
	print(mod_ncr(m - 1 + n - 1, m - 1, r))


def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
for T in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	print(mod_choose(n + m - 2, m - 1, 1000000007))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


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

def modular_mult(x, y):
	return x * y % MOD

def binomial_coeff(n, k):
	n_fac = reduce(modular_mult, range(k + 1, n + 1), 1)
	n_k_fac = reduce(modular_mult, range(1, n - k + 1), 1)
	return modular_mult(n_fac, pow(n_k_fac, MOD - 2, MOD))
t = int(input().strip())
for _ in range(t):
	(m, n) = tuple((int(i) for i in input().strip().split()))
	print(binomial_coeff(m + n - 2, n - 1))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


MOD = 10 ** 9 + 7

def getInvMod(m, n=None):
	if not n:
		n = m
	Inv = [None, 1]
	for i in range(2, n):
		Inv.append(-(m // i) * Inv[m % i] % m)
	return Inv
Inv = getInvMod(MOD, 10 ** 6 + 2)

def C(r, n):
	if r > n // 2:
		return C(n - r, n)
	if r < 0:
		return 0
	(c, i) = (1, 0)
	for i in range(r):
		c = c * (n - i) * Inv[i + 1] % MOD
	return c
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	print(C(m - 1, m + n - 2))


p = 10 ** 9 + 7

def fast_pow(a, k, p):
	if k == 0:
		return 1
	if k == 1:
		return a % p
	else:
		(q, r) = divmod(k, 2)
		res = fast_pow(a, q, p) % p
		square = res * res % p
		if r:
			return square * a % p
		else:
			return square

def f_modp(a, b, p):
	res = 1
	for i in range(a, b + 1):
		res = res * i % p
	return res

def binom_modp(n, m, p):
	num = f_modp(max(n - m, m) + 1, n, p)
	denom = f_modp(1, min(m, n - m), p)
	return num * fast_pow(denom, p - 2, p) % p
t = int(input().strip())
l = ''
for i in range(t):
	l = input().strip()
	(n, m) = [int(x) for x in l.split()]
	print(binom_modp(m + n - 2, m - 1, p))


mod = 10 ** 9 + 7

def gcd(n, m):
	if m == 0:
		return (1, 0)
	(a, b) = gcd(m, n % m)
	return (b, a - b * (n // m))

def inv(n):
	return gcd(n, mod)[0] % mod

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

def n_ch_k(n, k):
	return fac(n) * inv(fac(n - k) * fac(k)) % mod
t = int(input())
for _ in range(t):
	(n, m) = [int(e) for e in input().split()]
	print(n_ch_k(n + m - 2, n - 1))


def compute_factorials():
	factorials = [1]
	for i in range(1, MAX_M + MAX_N + 1):
		factorials.append(factorials[-1] * i % MOD)
	return factorials
MAX_M = 10 ** 6
MAX_N = 10 ** 6
MOD = 10 ** 9 + 7
factorials = compute_factorials()
t = int(input())
for _ in range(t):
	(m, n) = [int(x) for x in input().split()]
	numerator = factorials[m + n - 2]
	numerator *= pow(factorials[m - 1], MOD - 2, MOD)
	numerator *= pow(factorials[n - 1], MOD - 2, MOD)
	numerator %= MOD
	print(numerator)


def mod_prod(nums, mod):
	prod = 1
	for num in nums:
		prod = prod * num % mod
	return prod
p = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(n, m) = [int(k) for k in input().split()]
	r = m + n - 2
	k = min(n - 1, m - 1)
	print(mod_prod(range(r - k + 1, r + 1), p) * pow(mod_prod(range(1, k + 1), p), p - 2, p) % p)


t = int(input())

def modInverse(a, m):
	m0 = m
	t = 0
	q = 0
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1
for i in range(t):
	(m, n) = input().split(' ')
	m = int(m)
	n = int(n)
	p = 1
	q = 1
	for j in range(n - 1):
		p = p * (m + n - 2 - j) % 1000000007
		q = q * (1 + j) % 1000000007
	print(p * (modInverse(q, 1000000007) % 1000000007) % 1000000007)


MOD = int(1000000000.0 + 7)

def fpow(b, n):
	res = 1
	while n:
		if n & 1:
			res = res * b % MOD
		b = b * b % MOD
		n >>= 1
	return res

def rev(k):
	return fpow(k, MOD - 2)
ar = [0] * 2000001
ar[0] = 1
for i in range(1, 2000001):
	ar[i] = ar[i - 1] * i % MOD
for xx in range(int(input())):
	(n, m) = map(int, input().split())
	n -= 1
	m -= 1
	ans = ar[n + m] * rev(ar[n]) * rev(ar[m]) % MOD
	print(ans)


def egcd(a, b):
	if b == 0:
		return (1, 0, a)
	(x, y, d) = egcd(b, a % b)
	return (y, x - a // b * y, d)
K = 10 ** 9 + 7
L = 2 * 10 ** 6
f = [1 for i in range(L)]
for i in range(2, L):
	f[i] = f[i - 1] * i
	if f[i] >= K:
		f[i] %= K
inv = lambda a, m: egcd(a, m)[0]
for _ in range(int(input())):
	(m, n) = [int(s) for s in input().split()]
	d = f[m - 1] * f[n - 1] % K
	print(f[m + n - 2] * inv(d, K) % K)


from sys import stdin
modo = 10 ** 9 + 7

def inverseModN(nb, N):
	if not nb in dm:
		dm[nb] = pow(nb, N - 2, N)
	return dm[nb]

def zz(nz, N):
	if nz == N or nz == 1:
		return 1
	r = 1
	for z in range(1, nz):
		r = r * (N - z) * inverseModN(z, modo) % modo
	return r
dm = dict()
for _ in range(int(stdin.readline())):
	(x, y) = (int(i) for i in stdin.readline().strip().split())
	(x, y) = (y, x) if x > y else (x, y)
	print(zz(x, x + y - 1))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


prime = 1000000007

def factorial(x):
	if x <= 1:
		return 1
	result = 1
	while x:
		result = result * x % prime
		x -= 1
	return result

def pot(x, p):
	if p == 1:
		return x
	if p % 2:
		result = pot(x, p // 2)
		return result * result * x % prime
	else:
		result = pot(x, p // 2)
		return result * result % prime

def main():
	n = int(input())
	for i in range(n):
		(n, j) = map(int, input().split())
		if n + j <= 1:
			print(1)
		else:
			print(factorial(n + j - 2) * pot(factorial(n - 1) * factorial(j - 1), prime - 2) % prime)
main()


t = int(input().strip())

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):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	else:
		return x % m

def fact_gen(n):
	f = 1
	for i in range(1, n):
		yield f
		f *= i
		f %= 10 ** 9 + 7
fact = [i for i in fact_gen(2000000)]
for _ in range(t):
	(m, n) = [int(i) for i in input().strip().split(' ')]
	print(fact[n + m - 2] * modinv(fact[m - 1], 10 ** 9 + 7) * modinv(fact[n - 1], 10 ** 9 + 7) % (10 ** 9 + 7))


mod = 10 ** 9 + 7

def powermod(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	temp = powermod(a, b // 2)
	if b % 2 == 0:
		return (temp % mod) ** 2 % mod
	else:
		return a * (temp % mod) ** 2 % mod

def ncr(n, r):
	ans = 1
	denominator = 1
	for i in range(r + 1, n + 1):
		ans = ans % mod * i % mod
	for i in range(1, n - r + 1):
		denominator = denominator % mod * i % mod
	return ans * powermod(denominator, mod - 2) % mod
T = int(input())
for _ in range(T):
	(M, N) = tuple(map(int, input().split()))
	print(ncr(M + N - 2, M - 1))


from functools import reduce
md = int(1000000000.0 + 7)

def redd(x, y):
	return x * y

def redd_md(x, y):
	return x % md * (y % md) % md

def comb(n, k):
	k = min(k, n - k)
	pr_mod = reduce(redd_md, range(n - k + 1, n + 1), 1)
	k_factMod = pow(reduce(redd_md, range(1, k + 1), 1), md - 2, md)
	return int(pr_mod * k_factMod % md)
T = int(input())
for test in range(T):
	[m, n] = map(int, input().split(' '))
	print(comb(n + m - 2, n - 1))


from math import factorial
p = 10 ** 9 + 7
f = [1]
for i in range(1, 2000001):
	f.append(f[-1] * i % p)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(f[n + m - 2] * pow(f[n - 1], p - 2, p) * pow(f[m - 1], p - 2, p) % p)


def inverse(num, mod):
	r0 = mod
	r1 = num
	q0 = 0
	q1 = 0
	s0 = 0
	s1 = 1
	t0 = 1
	t1 = 0
	r = 1
	while r1 > 0:
		r = r1
		q = int(r0 / r1)
		r1 = r0 - q * r1
		r0 = r
		s = s1
		s1 = s0 - s1 * q
		s0 = s
		t = t1
		t1 = t0 - t1 * q
		t0 = t
	return s0

def prodrange(low, high):
	ans = 1
	p = 10 ** 9 + 7
	for i in range(low, high + 1):
		ans = ans * i % p
	return ans
T = input('')
dimenslist = []
append = dimenslist.append
for i in range(0, int(T)):
	dimens = input('')
	append(dimens.split())
p = 10 ** 9 + 7
for matri in dimenslist:
	m = int(matri[0])
	n = int(matri[1])
	if m == 1 or n == 1:
		print(1)
	else:
		row = m
		num = m + 1
		denom = 2
		i = 0
		denom = inverse(prodrange(2, n - 1), p) % p
		num = prodrange(num, n + m - 2)
		ans = row * denom * num % p
		print(ans)


Base = 10 ** 9 + 7

def modPower(X, Y, M):
	answer = 1
	remains = Y
	powered = X
	while remains > 0:
		if remains % 2 == 1:
			answer = answer * powered % M
		remains //= 2
		powered = powered * powered % M
	return answer

def modDiv(X, Y, M):
	return X * modPower(Y, M - 2, M) % M

def nCr(N, R):
	num = 1
	dem = 1
	for i in range(1, R + 1):
		num = num * (N + 1 - i) % Base
		dem = dem * i % Base
	answer = modDiv(num, dem, Base)
	return answer
T = int(input())
for i in range(0, T):
	(M, N) = map(int, input().split())
	print(nCr(M + N - 2, N - 1))


module = 10 ** 9 + 7

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

def inverse(a, m=module):
	(x, y, g) = gcdex(a, m)
	if g != 1:
		return -1
	else:
		return (x % m + m) % m
N = 10 ** 6
f = [1] * (2 * N + 1)
for i in range(1, 2 * N + 1):
	f[i] = f[i - 1] * i % module
for t in range(int(input())):
	(n, m) = map(int, input().split())
	print(f[n + m - 2] * inverse(f[n - 1]) * inverse(f[m - 1]) % module)


mod = 1000000007

def mpow(a, n):
	p = 1
	while n > 0:
		if n % 2 == 1:
			p = p * a % mod
		a = a * a % mod
		n = n // 2
	return p
MAX = 2000000
F = [1] * MAX
for i in range(2, MAX):
	F[i] = i * F[i - 1] % mod
t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	inv = mpow(F[m - 1] * F[n - 1] % mod, mod - 2)
	r = F[m + n - 2] * inv % mod
	print(r)


def gcd_ext(a, b):
	s0 = 1
	s1 = 0
	while b:
		(q, r) = divmod(a, b)
		(a, b) = (b, r)
		(s0, s1) = (s1, s0 - q * s1)
	return (a, s0)

def binom(n, k, mod):
	if k > n // 2:
		k = n - k
	numerator = 1
	denominator = 1
	for i in range(k):
		numerator = numerator * (n - i) % mod
		denominator = denominator * (i + 1) % mod
	(dummy, r) = gcd_ext(denominator, mod)
	return numerator * r % mod
for i in range(int(input())):
	(m, n) = map(int, input().split())
	print(binom(m + n - 2, m - 1, 1000000007))


M = 10 ** 9 + 7

def factorial(n):
	r = 1
	for i in range(1, n + 1):
		r = r * i % M
	return r

def euclide(a, b):
	if a < 0:
		r = euclide(-a, b)
		return (r[0], -r[1], r[2])
	if b < 0:
		r = euclide(a, -b)
		return (r[0], r[1], -r[2])
	if b == 0:
		return (a, 1, 0)
	r = euclide(b, a % b)
	return (r[0], r[2], r[1] - a // b * r[2])

def invert(n):
	return euclide(n, M)[1] % M

def Cnk(n, k):
	return factorial(n) * invert(factorial(k)) * invert(factorial(n - k)) % M
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	print(Cnk(m + n - 2, n - 1))


import math

def fact(n, p):
	prod = 1
	if n >= p:
		return 0
	for i in range(1, n + 1):
		prod = prod * i % p
	return prod

def solve(m, n):
	x = fact(m + n - 2, 1000000007)
	y = pow(fact(m - 1, 1000000007) * fact(n - 1, 1000000007), 1000000005, 1000000007)
	return x * y % 1000000007
T = int(input())
for i in range(0, T):
	nums = input()
	(m, n) = nums.split()
	m = int(m)
	n = int(n)
	print(solve(m, n))


P = 10 ** 9 + 7
factors = [1]

def make_factors():
	for i in range(1, 2 * 10 ** 6):
		k = i * factors[-1] % P
		factors.append(k)

def gcdex(a):
	n = P
	b = a
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return x0 % P

def f(m, n):
	ch = factors[n]
	zn = gcdex(factors[m] * factors[n - m] % P)
	return ch * zn % P
make_factors()
T = int(input())
for i in range(T):
	(m, n) = (int(j) for j in input().split())
	print(f(m - 1, m + n - 2))


def inv(a):
	s = 0
	olds = 1
	t = 1
	oldt = 0
	r = 1000000007
	oldr = a
	while r != 0:
		quotient = oldr // r
		(oldr, r) = (r, oldr - quotient * r)
		(olds, s) = (s, olds - quotient * s)
		(oldt, t) = (t, oldt - quotient * t)
	return olds % 1000000007
for test in range(int(input())):
	(m, n) = [int(s) for s in input().split(' ')]
	num = 1
	multnum = 1
	multden = 1
	p = m + n - 2
	for k in range(min([m, n]) - 1):
		multnum = multnum * p % 1000000007
		multden = multden * (k + 1) % 1000000007
		p = p - 1
	num = num * multnum * inv(multden) % 1000000007
	print(num)


modprime = 10 ** 9 + 7

def modmul(a, b):
	return a % modprime * (b % modprime) % modprime

def modinverse(x):
	return pow(x, modprime - 2, modprime)

def moddiv(a, b):
	return modmul(a, modinverse(b))

def modfact():
	yield 1
	i = 1
	fact = 1
	while True:
		fact *= i
		fact %= modprime
		yield fact
		i += 1
modfactgen = modfact()
modfactorials = [next(modfactgen) for i in range(2 * 10 ** 6)]

def modbinomial(n, k):
	return moddiv(modfactorials[n], modmul(modfactorials[k], modfactorials[n - k]))
T = int(input())
for t in range(T):
	(m, n) = map(int, input().split())
	m -= 1
	n -= 1
	print(modbinomial(m + n, n))


magicmod = 10 ** 9 + 7
invmem = [None] * 1000001

def inv(n):
	if invmem[n] is None:
		(x_new, x) = (1, 0)
		(r_new, r) = (n, magicmod)
		while r_new:
			(r, (q, r_new)) = (r_new, divmod(r, r_new))
			(x, x_new) = (x_new, x - q * x_new)
		invmem[n] = x
	return invmem[n]

def choose(n, r):
	r = min(r, n - r)
	res = 1
	while r:
		res = res * n * inv(r) % magicmod
		n -= 1
		r -= 1
	return res
T = int(input())
for t in range(T):
	(m, n) = map(int, input().split())
	res = choose(m + n - 2, m - 1)
	print(res % magicmod)


mod = 1000000007
t = int(input())
gt = [1]
for i in range(1, 2000001):
	gt.append(gt[i - 1] * i % mod)

def pow(a, b):
	if b == 1:
		return a
	x = pow(a, b // 2)
	ret = x * x % mod
	if b % 2 == 1:
		ret = ret * a % mod
	return ret
for _ in range(t):
	(m, n) = map(int, input().split())
	ret = gt[m + n - 2] * pow(gt[n - 1], mod - 2) * pow(gt[m - 1], mod - 2) % mod
	print(ret)


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

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()))
	if N > 1 and M > 1:
		print(fact[N + M - 2] * (power(fact[N - 1] * fact[M - 1] % MOD, MOD - 2) % MOD) % MOD)
	else:
		print(1)


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

def egcd(a0, a1):
	(x0, x1, y0, y1, b, n) = (1, 0, 0, 1, a0, a1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(n, p):
	return egcd(n, p)[1] % p

def nCm(n, m, p):
	m = m if m * 2 <= n else n - m
	a = reduce(lambda x, y: x * y % p, range(n - m + 1, n + 1), 1)
	b = reduce(lambda x, y: x * y % p, range(1, m + 1), 1)
	return a * modinv(b, p) % p
T = int(input().strip())
for _ in range(T):
	(N, M) = list(map(int, input().strip().split()))
	(N, M) = (N - 1, M - 1)
	print(nCm(N + M, M, P))


def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		a = 1
		b = 1
		for t in range(min(k, n - k)):
			a *= n - t
			b *= t + 1
			a %= 10 ** 9 + 7
			b %= 10 ** 9 + 7
		return a * pow(b, 10 ** 9 + 5, 10 ** 9 + 7) % (10 ** 9 + 7)
T = int(input())
for i in range(T):
	s = input().split()
	m = int(s[0])
	n = int(s[1])
	print(choose(m + n - 2, m - 1))


p = 1000000007

def exp(base, exp):
	res = 1
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % p
		base = base * base % p
		exp = exp // 2
	return res % p

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

def modBinomial(n, k):
	numerator = 1
	for i in range(k):
		numerator = numerator * (n - i) % p
	denominator = 1
	for i in range(1, k + 1):
		denominator = denominator * i % p
	return numerator * modInverse(denominator) % p
t = int(input())
while t > 0:
	t -= 1
	(m, n) = list(map(int, input().split()))
	one = m - 1
	total = m + n - 2
	print(modBinomial(total, one))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
a = []
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))
for i in range(len(a)):
	print(a[i])


def fattoriale(n):
	if n > 750000:
		risultato = 419049924
		inizio = 750001
	elif n > 500000:
		risultato = 154425679
		inizio = 500001
	elif n > 250000:
		risultato = 50180518
		inizio = 250001
	else:
		risultato = 1
		inizio = 2
	for i in range(inizio, n + 1):
		risultato = risultato * i % (10 ** 9 + 7)
	return risultato

def potenza(base, esp):
	if base == 1:
		return 1
	p = 10 ** 9 + 7
	x1 = base
	lista_x_esp = []
	lista_esp = []
	esp_tot = 1
	while esp >= esp_tot:
		esp1 = 2
		while x1 ** esp1 < p:
			esp1 += 1
		x1 = x1 ** esp1 % p
		esp_tot = esp_tot * esp1
		lista_x_esp.append((x1, esp_tot))
		if x1 == 1:
			lista_x_esp.append((1, 1))
			break
	esp_rimanente = esp
	resto = 1
	for x_esp in lista_x_esp[-2::-1]:
		if esp_rimanente > x_esp[1]:
			resto *= x_esp[0] ** (esp_rimanente // x_esp[1])
			esp_rimanente %= x_esp[1]
	if esp_rimanente != 0:
		resto *= base ** esp_rimanente
	return resto % p
t = int(input().strip())
for i in range(t):
	(n, m) = [int(x) - 1 for x in input().strip().split(' ')]
	fatt_m_inverso = fattoriale(m)
	fatt_m_inverso = potenza(fatt_m_inverso, 10 ** 9 + 5)
	fatt_n_inverso = fattoriale(n)
	fatt_n_inverso = potenza(fatt_n_inverso, 10 ** 9 + 5)
	print(fattoriale(n + m) * fatt_n_inverso * fatt_m_inverso % (10 ** 9 + 7))


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

def modinv(x, n):
	(g, inv, _) = egcd(x, n)
	if g == 1:
		return inv % n
mod = 1000000007
F = [1]
for i in range(1, 2000001):
	F.append(F[-1] * i % mod)
t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	S = F[m + n - 2] * modinv(F[m - 1] * F[n - 1], mod)
	S %= mod
	print(S % 1000000007)


from functools import reduce

def pulverize(a, b):
	(u, v) = ((1, 0), (0, 1))
	while b:
		(q, r) = divmod(a, b)
		(a, b) = (b, r)
		(u, v) = (v, (u[0] - q * v[0], u[1] - q * v[1]))
	return u

def traces(m, n):
	(r, s) = (min(m, n) - 1, m + n - 2)
	n = reduce(lambda x, y: x * y % 1000000007, range(s, s - r, -1), 1)
	d = reduce(lambda x, y: x * y % 1000000007, range(1, r + 1), 1)
	inverse_d = pulverize(d, 1000000007)[0] % 1000000007
	return n * inverse_d % 1000000007
t = int(input())
for t0 in range(t):
	(m, n) = input().strip().split()
	(m, n) = (int(m), int(n))
	print(traces(m, n))


modulo = 10 ** 9 + 7

def powup(a, n):
	if n == 0:
		return 1
	else:
		p = powup(a, n // 2)
		if n % 2 == 0:
			return p * p % modulo
		else:
			return p * p % modulo * a % modulo

def factorial(n):
	p = 1
	for i in range(2, n + 1):
		p = p * i % modulo
	return p
t = int(input())
for i in range(t):
	s = input().split(' ')
	(m, n) = (int(s[0]), int(s[1]))
	print(factorial(m + n - 2) * powup(factorial(n - 1) * factorial(m - 1), modulo - 2) % modulo)


from fractions import gcd

def reduce(p, up, x, step):
	while p < len(up):
		g = gcd(x, up[p])
		x //= g
		up[p] //= g
		if x == 1:
			break
		p += step
	return x

def comb(n, k, z):
	m = n - k + 1
	up = 1
	for i in range(m, n + 1):
		up = up * i % z
	bottom = 1
	for i in range(2, k + 1):
		bottom = bottom * i % z
	res = up * pow(bottom, z - 2, z) % z
	return res

def compute(m, n):
	z = 10 ** 9 + 7
	return comb(m + n - 2, min(m, n) - 1, z)
T = int(input())
for i in range(T):
	s = input()
	vals = [int(x) for x in s.split(' ')]
	m = vals[0]
	n = vals[1]
	print(compute(m, n))


PRIME = 10 ** 9 + 7
fact = [1, 1] + [0] * 2000003
for i in range(2, 2000001):
	fact[i] = i * fact[i - 1] % PRIME

def inv_fact(r):
	return pow(fact[r], PRIME - 2, PRIME)

def ncr(n, r):
	return fact[n] * inv_fact(r) * inv_fact(n - r)
t = int(input())
for _ in range(t):
	(n, m) = (int(i) for i in input().split())
	print(ncr(n + m - 2, n - 1) % PRIME)


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

def fastexpo(a, n):
	ret = 1
	b = a
	while n:
		if n & 1:
			ret = ret * b % k
		b = b * b % k
		n >>= 1
	return ret
fac = [k - 1] * 2000001
fac[0] = 1
for i in range(2000000):
	fac[i + 1] = (i + 1) * fac[i] % k
t = int(input())
for _ in range(t):
	(m, n) = [int(x) - 1 for x in input().split()]
	if m == 0 or n == 0:
		print(1)
	else:
		fmn = fac[m + n]
		fm = fac[m]
		fn = fac[n]
		fmfni = fastexpo(fm * fn, k - 2)
		x = fmn * fmfni
		print(x % k)


def factm(x, memo=[1]):
	if len(memo) < x + 1:
		n = len(memo)
		for i in range(n, x + 1):
			memo.append(i * memo[-1] % 1000000007)
	return memo[x]

def f(j, k):
	v = 1
	for i in range(k + 1, j + k + 1):
		v *= i
		v %= 1000000007
	return v * pow(factm(j), 1000000005, 1000000007) % 1000000007
for _ in range(int(input())):
	(m, n) = sorted([int(x) for x in input().strip().split()])
	print(f(m - 1, n - 1))


M = 10 ** 9 + 7
fac = [1] * 2000001
for i in range(1, 2000001):
	fac[i] = i * fac[i - 1] % M

def extendedEu(a, b):
	m = a // b
	r = a % b
	if b % r == 0:
		return (1, m, r)
	(p, q, gcd) = extendedEu(b, r)
	return (-q, -(q * m + p), gcd)

def modinv(x):
	return extendedEu(x, M)[0]

def nCk(n, k):
	return fac[n] * modinv(fac[n - k] * fac[k]) % M
q = int(input())
for _ in range(q):
	(m, n) = [int(x) for x in input().split()]
	print(nCk(n + m - 2, n - 1))


from functools import reduce
N = int(1000000000.0) + 7

def mul(a, b):
	return a * b % N

def div(a, b):
	return mul(a, pow(b, N - 2, N))

def factorial_cache(n):
	data = [None] * (n + 1)
	data[0] = 1
	for i in range(1, len(data)):
		data[i] = mul(data[i - 1], i)
	return data

def choose(n, k, cache):
	numerator = cache[n]
	denominator = mul(cache[n - k], cache[k])
	return div(numerator, denominator)
t = int(input())
q = [tuple(map(int, input().split())) for _ in range(t)]
max_factorial = max((sum(x) - 2 for x in q))
cache = factorial_cache(max_factorial)
for (n, m) in q:
	print(choose(n + m - 2, min(n - 1, m - 1), cache))


import sys
MOD = 1000000007

def modinv(n, p):
	return pow(n, p - 2, p)

def mod_choose(n, k, m):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p = p * n % m
			q = q * i % m
			n -= 1
		return p * modinv(q, m) % m
T = int(sys.stdin.readline())
for _ in range(T):
	(m, n) = [int(x) for x in sys.stdin.readline().split()]
	print(mod_choose(n + m - 2, m - 1, MOD))


MOD = 10 ** 9 + 7
T = int(input())
debug = False
debug1 = False

def modpow(a, b, mod):
	x = 1
	y = a
	if debug1:
		print('modpow({},{},{}), x = {}, y = {}'.format(a, b, mod, x, y))
	while b > 0:
		if b % 2 == 1:
			if debug1:
				print('  b == {}, x * y = {}'.format(b, x * y))
			x *= y
			if x > mod:
				x %= mod
		y *= y
		if y > mod:
			y %= mod
		b //= 2
		if debug1:
			print('  b = {}, x = {}, y = {}'.format(b, x, y))
	return x

def modInverse(a, mod):
	retval = modpow(a, mod - 2, mod)
	if debug:
		print('Mod inverse of {} for {} is {}'.format(a, mod, retval))
	return retval

def facm(n):
	i = 1
	for x in range(n, 1, -1):
		i *= x
		i %= MOD
	return i
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	N -= 1
	M -= 1
	if N < M:
		(N, M) = (M, N)
	J = N + M
	J1 = J
	r = 1
	num = 1
	denom = 1
	for i in range(1, M + 1):
		num *= J1
		num %= MOD
		J1 -= 1
		denom *= i
		denom %= MOD
	denominv = modInverse(denom, MOD)
	r = num * denominv % MOD
	print(r)


def prod(a, b):
	p = 1
	for i in range(a, b + 1):
		p = p % m * (i % m) % m
	return p

def expo(n):
	p = 1
	x = len(k)
	for i in range(x):
		if k[i] == '1':
			p = p % m * (n % m) % m
		if i != x - 1:
			n = n % m * (n % m) % m
	return p
k = bin(1000000005)[2:][::-1]
m = 1000000007
for _ in range(int(input())):
	(r, c) = [int(x) for x in input().split()]
	if r > c:
		print(prod(r, r + c - 2) * expo(prod(1, c - 1)) % m)
	else:
		print(prod(c, r + c - 2) * expo(prod(1, r - 1)) % m)


def mod_exp(b, e, mod):
	r = 1
	while e > 0:
		if e & 1 == 1:
			r = r * b % mod
		b = b * b % mod
		e >>= 1
	return r

def fermat_binom(n, k, p):
	if k > n:
		return 0
	num = 1
	for i in range(n, n - k, -1):
		num = num * i % p
	denom = 1
	for i in range(1, k + 1):
		denom = denom * i % p
	return num * mod_exp(denom, p - 2, p) % p
m = 10 ** 9 + 7
n = int(input())
c = []
for y in range(n):
	arr = [int(x) for x in input().split()]
	c.append(arr)
for x in c:
	t_steps = sum(x) - 2
	d_steps = x[0] - 1
	print(fermat_binom(t_steps, d_steps, m))


def decreasingproduct(a, b):
	acc = 1
	for i in range(a, b, -1):
		acc = acc * i % (10 ** 9 + 7)
	return acc

def invert(a):
	exp = 10 ** 9 + 5
	acc = 1
	tmp = a
	k = 2
	while exp > 0:
		if exp % k != 0:
			acc = acc * tmp % (10 ** 9 + 7)
			exp -= k // 2
		k = 2 * k
		tmp = tmp ** 2 % (10 ** 9 + 7)
	return acc
T = int(input())
for t in range(T):
	mn = [int(x) for x in input().split()]
	m = mn[0]
	n = mn[1]
	num = decreasingproduct(m + n - 2, m - 1)
	denom = decreasingproduct(n - 1, 1)
	prod = num * invert(denom) % (10 ** 9 + 7)
	print(prod)


import sys
import math
arr = list(map(lambda x: x.strip(), sys.stdin.readlines()))

def fact(n):
	i = 1
	prod = 1
	while i <= n:
		prod = prod * i
		prod = prod % (pow(10, 9) + 7)
		i = i + 1
	return prod

def qFact(n, m):
	i = n - 1
	prod = n
	while i > m:
		prod = prod * i
		prod = prod % (pow(10, 9) + 7)
		i = i - 1
	return prod

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
arr = arr[1:]
for lin in arr:
	nums = lin.split()
	m = int(nums[0])
	n = int(nums[1])
	if n > 10 and m > 10:
		ans = fact(m - 1)
		ans = modinv(ans, pow(10, 9) + 7)
		ans = ans * qFact(m + n - 2, n - 1)
		ans = ans % (pow(10, 9) + 7)
		print(ans)
	else:
		ans = math.factorial(n + m - 2) // (math.factorial(n - 1) * math.factorial(m - 1))
		print(ans)


t = int(input())
p = 10 ** 9 + 7

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

def modinv(a, p):
	return modp(a, p - 2, p)

def modbinomial(n, r, p):
	num = 1
	for i in range(n, n - r, -1):
		num = num * i % p
	denom = 1
	for i in range(1, r + 1):
		denom = denom * i % p
	return num * modinv(denom, p) % p
while t > 0:
	(m, n) = [int(x) for x in input().split(' ')]
	print(modbinomial(m + n - 2, m - 1, p))
	t -= 1


mod = 1000000007

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, y // 2) ** 2 % mod
	else:
		return power(x, y // 2) ** 2 * x % mod
F = {}
F[0] = 1
invF = {}
a = 1
for i in range(1, 2 * 10 ** 6):
	a *= i
	a %= mod
	F[i] = a
invF = [0] * (2 * 10 ** 6)
invF[2 * 10 ** 6 - 1] = power(F[2 * 10 ** 6 - 1], mod - 2)
for n in range(2 * 10 ** 6 - 2, -1, -1):
	invF[n] = invF[n + 1] * (n + 1) % mod

def combi(n, m):
	return F[n] * invF[m] * invF[n - m] % mod
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = combi(n + m - 2, n - 1)
	print(ans % mod)


import sys
mod = 1000000007

def modinv(a):
	ap = mod
	(s, sp, t, tp) = (0, 1, 1, 0)
	while a != 0:
		q = ap // a
		(ap, a) = (a, ap % a)
		(sp, s) = (s, sp - q * s)
		(tp, t) = (t, tp - q * t)
	return (tp + mod) % mod
t = int(input())
while t > 0:
	t = t - 1
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	(a, b) = (a - 1, b - 1)
	ans1 = 1
	for i in range(a + 1, a + b + 1):
		ans1 = ans1 * i % mod
	ans2 = 1
	for i in range(1, b + 1):
		ans2 = ans2 * i % mod
	ans2 = modinv(ans2)
	print(ans1 * ans2 % mod)


from functools import reduce
import operator as op
import math

def nCk_mod(n, k, mod):
	top = reduce(lambda a, b: a * b % mod, range(n - k + 1, n + 1), 1)
	bottom = reduce(lambda a, b: a * b % mod, range(1, k + 1), 1)
	bottom = pow(bottom, mod - 2, mod)
	return top * bottom % mod
for t in range(int(input())):
	(n, m) = [int(x) for x in input().strip().split()]
	(n, m) = (n + m - 2, min(n, m) - 1)
	k = min(m, n - m)
	print(nCk_mod(n, k, 10 ** 9 + 7))


from math import factorial

def alt_fact(n):
	product = 1
	for i in range(n + 1):
		if i > 0:
			product *= i
			product = product % mod_val
	return int(product)
num_tests = int(input())
mod_val = 10 ** 9 + 7

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
for i in range(num_tests):
	(m, n) = input().strip().split(' ')
	(m, n) = [int(m), int(n)]
	p1 = 1
	min_dim = min(m, n)
	for i in range(min_dim, m + n - 1):
		p1 *= i
		p1 = p1 % mod_val
	denom = alt_fact(m + n - 1 - min_dim)
	denom = pow(denom, mod_val - 2, mod_val)
	print(int(p1 * denom % mod_val))


import functools

@functools.lru_cache(maxsize=None)
def pow__mod_c(a, k, c):
	if k == 0:
		return 1
	elif k & 1:
		return a * pow__mod_c(a, k // 2, c) ** 2 % c
	else:
		return pow__mod_c(a, k // 2, c) ** 2 % c

def n_choose_k__mod_c(n, k, c):
	numerator = 1
	for i in range(n - k + 1, n + 1):
		numerator *= i
		numerator %= c
	denominator = 1
	for i in range(1, k + 1):
		denominator *= i
		denominator %= c
	denominator = pow__mod_c(denominator, c - 2, c)
	return numerator * denominator % c
T = int(input())
inputs = [input().split() for _ in range(T)]
A = [(int(x[0]), int(x[1])) for x in inputs]
c = 10 ** 9 + 7
for (m, n) in A:
	print(n_choose_k__mod_c(m + n - 2, n - 1, c))


t = int(input())

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

def fact(a, b):
	res = 1
	for i in range(a, b + 1):
		res *= i
		res %= 1000000007
	return res
for i in range(t):
	line = input().split(' ')
	m = int(line[0]) - 1
	n = int(line[1]) - 1
	if m > n:
		top = int(fact(m + 1, m + n))
		bot = int(fact(1, n))
		botInv = modInv(bot, 1000000007)
		print(top * botInv % 1000000007)
	else:
		top = int(fact(n + 1, m + n))
		bot = int(fact(1, m))
		botInv = modInv(bot, 1000000007)
		print(top * botInv % 1000000007)


M = 1000000000 + 7
fact = [1]
for i in range(1, 2000000 + 1):
	fact += [i * fact[-1] % M]

def inv(n):
	return pow(n, M - 2, M)

def C(n, m):
	return fact[n] * inv(fact[m]) * inv(fact[n - m]) % M
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	print(C(n + m - 2, n - 1))


def modFact(b, s, m):
	res = 1
	for x in range(b - s + 1):
		res = res * (b - x) % m % m
	return res

def fexp(b, n, m):
	res = 1
	while n:
		if n % 2 == 1:
			res = res * b % m
		b = b * b % m
		n = n // 2
	return res
import math as M
for _ in range(int(input())):
	(n, m) = input().split(' ')
	(n, m) = (int(n), int(m))
	md = 7 + pow(10, 9)
	ans = modFact(m + n - 2, m, md) * fexp(modFact(n - 1, 1, md), md - 2, md) % md
	print('{0}'.format(ans))


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

def prod(a, b):
	return a * b % mod

def fastExp(a, b):
	x = 1
	y = a
	while b > 0:
		if b % 2:
			x = x * y % mod
		y = y * y % mod
		b //= 2
	return x

def ncr(n, r):
	if n == r:
		return 1
	nr = reduce(prod, [i % mod for i in range(n - r + 1, n + 1)])
	dr = reduce(prod, [i % mod for i in range(1, r + 1)])
	return nr * fastExp(dr, mod - 2) % mod
for _ in range(int(input())):
	(m, n) = [int(i) for i in input().split()]
	print(ncr(m + n - 2, max(m, n) - 1) % (10 ** 9 + 7))