Read problems statements in Mandarin Chinese  and Russian. 

Devu is learning Combinatorics in his college. He find it very interesting to calculate number of ways of going to point (c,d) from point (a,b) in co-ordinate plane. We can take horizontal and vertical steps only and can not visit at a point twice. In a step, you can move one unit only. We have to reach to the point (c,d) from the point (a,b) using abs(a-c)+ abs(b-d) steps only.

Devu has two sets of points. Set A contains points having X co-ordinate 0 and Y co-ordinates varying from 1 to N(both inclusive). Set B contains points having X co-ordinate K and Y co-ordinates varying from 1 to N(both inclusive).  Both sets contains N number of integral points. He wants to calculate the sum of number of ways to going to the each point of set B from the each point of set A .

As the answer can be large, print it modulo 1000000007.
 
------ Input ------ 

First line of input contains an integer T denoting number of test cases.  
Next T lines will contain pair of integers N and K

------ Output ------ 

For each test case, print a single integer representing the answer of that test case.

------ Constraints ------ 

Subtask #1: 10 points

	$1 ≤ T  ≤ 20, 1 ≤ N ,K ≤ 1000$

Subtask #1: 10 points

	$1 ≤ T  ≤ 20, 1 ≤ N ,K ≤ 10^{6}$

Subtask #3: 80 points

	$1 ≤ T  ≤ 10000, 1 ≤ N,K  ≤ 10^{6}$

----- Sample Input 1 ------ 
2

2 2

4 5
----- Sample Output 1 ------ 
8

236
----- explanation 1 ------ 

For the first sample case,
ways[(0,1)->(2,1)]= 1
ways[(0,2)->(2,2)]= 1
ways[(0,1)->(2,2)]= 3
ways[(0,2)->(2,1)]= 3

So, the total number of ways = 8.

Source: codechef | Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics


Solutions:
(limit, MOD) = (int(2 * 10 ** 6 + 10), int(10 ** 9) + 7)
(factorial, invFactorial) = ([0] * limit, [0] * limit)

def calFactorial():
	limit = int(2 * 10 ** 6 + 10)
	(factorial[0], factorial[1], invFactorial[0], invFactorial[1]) = (1, 1, 1, 1)
	for i in range(2, limit):
		factorial[i] = factorial[i - 1] * i % MOD
	for i in range(2, limit):
		invFactorial[i] = (MOD - MOD // i * invFactorial[MOD % i]) % MOD
	for i in range(1, limit):
		invFactorial[i] = invFactorial[i - 1] * invFactorial[i] % MOD

def nCr(N, R):
	if R > N:
		return 0
	ans = factorial[N] * invFactorial[R] % MOD * invFactorial[N - R]
	ans %= MOD
	return ans

def solve(N, K):
	ans = 2 * nCr(N + K + 1, K + 2) - N
	ans = (ans % MOD + MOD) % MOD
	print(ans)
calFactorial()
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	solve(N, K)


t = int(input())
q = [1]
for i in range(1, 2000002):
	q.append(q[-1] * i % (10 ** 9 + 7))
inv = lambda x: pow(q[x], 10 ** 9 + 5, 10 ** 9 + 7)
for i in range(t):
	(n, k) = map(int, input().split())
	print((2 * q[k + n + 1] * inv(k + 2) * inv(n - 1) - n) % (10 ** 9 + 7))


def power(a, n):
	res = 1
	while n:
		if n % 2 == 1:
			res = res * a % p
			n -= 1
		else:
			a = a * a % p
			n = n // 2
	return res

def c(n, k):
	if k > n:
		return 0
	res = f[n]
	res = res * power(f[k], p - 2) % p
	res = res * power(f[n - k], p - 2) % p
	return res % p
p = 10 ** 9 + 7
f = [0] * (2100000 + 2)
f[0] = f[1] = 1
for i in range(2, 2100000 + 2):
	f[i] = i * f[i - 1] % p
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = c(n + k + 1, k + 2)
	print((2 * int(m) - n + p) % p)


factorial = [1]
mod = 10 ** 9 + 7
for i in range(1, 3000000):
	a = factorial[-1] * i % mod
	factorial.append(a)

def C(a, b):
	if b > a:
		return 0
	num = factorial[a]
	den = factorial[b] * factorial[a - b] % mod
	inverse = pow(den, mod - 2, mod)
	answer = num * inverse % mod
	return answer

def solve2(N, K):
	num = ((N + 1) * C(K + N + 1, K) - (K ** 2 + 3 * K + 2)) % mod
	num *= 2
	num = num * N % mod
	den = (K + 1) * (K + 2) % mod
	inverse = pow(den, mod - 2, mod)
	answer = num * inverse % mod
	return (answer + N) % mod
for i in range(int(input())):
	(N, K) = map(int, input().split())
	print(solve2(N, K))


fac = []
m = int(1000000000.0 + 7)
fac.append(1)
for i in range(1, 2 * 10 ** 6 + 2):
	temp = fac[i - 1] % m * i % m % m
	fac.append(temp)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	res = (2 * (fac[n + k + 1] * pow(fac[n - 1], m - 2, m) * pow(fac[k + 2], m - 2, m)) - n) % m
	print(res)


mod = 10 ** 9 + 7
t = int(input())
fact = [1]
for i in range(1, 2000002):
	fact.append(fact[-1] * i % mod)
inv = lambda x: pow(fact[x], mod - 2, mod)
for _ in range(t):
	(n, k) = map(int, input().split())
	print((2 * fact[k + n + 1] * inv(k + 2) * inv(n - 1) - n) % mod)


T = int(input())
fact = [1 for x in range(2000005)]
mod = 1000000007
for x in range(1, 2000005):
	fact[x] = x * fact[x - 1] % mod
for y in range(T):
	(n, k) = map(int, input().split())
	ans = fact[n + k + 1] * pow(fact[k + 2] * fact[n - 1], mod - 2, mod) % mod
	ans = (2 * ans + mod - n) % mod
	print(ans)


mod = 1000000007
arr = [1]
for i in range(1, 2000006):
	arr.append(arr[i - 1] * i % mod)
x = int(input())
for i in range(x, 0, -1):
	(n, k) = map(int, input().split())
	num = 2 * n * (n + k + 1) * arr[n + k] % mod
	den1 = pow((k + 1) * (k + 2) * arr[k], mod - 2, mod)
	den2 = pow(arr[n], mod - 2, mod)
	res = (num * den1 * den2 - n) % mod
	print(int(res))


M = 1000000007
N = 2000005
F = [0] * N
F[0] = 1
for i in range(1, N):
	F[i] = F[i - 1] * i % M
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	ans = F[n + k + 1] * pow(F[k + 2], M - 2, M) * pow(F[n - 1], M - 2, M) % M * 2 - n + M
	print(ans % M)