Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.
.

Chef offers delicious food in his restaurant, but he wants to make it a more attractive place too.

The guests in the restaurant usually walk along a path consisting of two adjacent, parallel rows of square bricks leading to the entrance. Each row is $N$ bricks long, all bricks have the same size and there are no holes.

Unfortunately, the path looks pretty boring because all bricks have the same color. In order to make it more interesting, Chef wants to replace exactly $K$ bricks by more beautiful ones in such a way that no two replaced bricks share a side.

Chef asks you to answer a question that is too complicated for him: in how many ways can Chef select the bricks to replace? Since the answer can be very large, compute it modulo $10^{9} + 7$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $N$ and $K$.

------  Output ------
For each test case, print a single line containing one integer — the number of ways to replace bricks, modulo $10^{9} + 7$.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 1,000$

------  Subtasks: ------
Subtask #1 (25 points): $1 ≤ N ≤ 1,000$ 

Subtask #2 (75 points): original constraints

----- Sample Input 1 ------ 
1
3 2
----- Sample Output 1 ------ 
8
----- explanation 1 ------ 
Example case 1: There are exactly $8$ valid ways to choose the positions of $K = 2$ beautiful bricks.

Source: codechef | Difficulty: HARD
Tags: Combinatorics

Preprocessing

Complete search

Mathematics

Matrices


Solutions:
import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from functools import reduce
import operator as op
MOD = 10 ** 9 + 7

def ncr(n, m):
	if m > n:
		return 0
	numer = reduce(op.mul, range(n, n - m, -1), 1)
	denom = reduce(op.mul, range(1, m + 1), 1)
	return numer // denom

def solve(N, K):
	if N < K:
		return 0
	ans = 0
	for x in range(K):
		t = ncr(K - 1, x)
		t *= 2 ** (x + 1)
		t %= MOD
		t *= ncr(N - K + 1, x + 1)
		t %= MOD
		ans += t
		ans %= MOD
	return ans
T = int(input())
for ti in range(T):
	(N, K) = map(int, input().split())
	print(solve(N, K))


def modinv(a, m):
	ap = m
	(tp, t) = (0, 1)
	while a > 1:
		(q, b) = divmod(ap, a)
		(tp, t) = (t, tp - q * t)
		(ap, a) = (a, b)
	return t % m
mdl = 1000000007
inv = [modinv(a, mdl) for a in range(1002)]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0:
		print(1)
		continue
	p = n - k
	if p < 0:
		print(0)
		continue
	p2 = 2
	spl = 0
	sop = 1
	ins = p + 1
	tot = p2 * sop * ins % mdl
	while spl < k - 1 and spl < p:
		spl += 1
		p2 = p2 * 2 % mdl
		sop = sop * (k - spl) * inv[spl] % mdl
		ins = ins * (p + 1 - spl) * inv[spl + 1] % mdl
		tot = (tot + sop * ins * p2) % mdl
	print(tot)


def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s

def solve(N, k, p=10 ** 9 + 7):
	res = 0
	for i in range(1, min(k + 1, N - k + 2)):
		res = (res + pow(2, i, p) * choose(k - 1, i - 1, p) * choose(N - k + 1, i, p)) % p
	return res

def choose(a, b, p):
	assert a >= b
	num = 1
	for i in range(a - b + 1, a + 1):
		num = num * i % p
	den = 1
	for i in range(1, b + 1):
		den = den * i % p
	return num * modular_inverse(den, p) % p
T = int(input())
for test in range(T):
	(N, k) = [int(v) for v in input().split()]
	print(solve(N, k))


c1 = []
c2 = []
modu = 1000000007

def nc(k, r):
	for i in range(1, k):
		c1.append(c1[i - 1] * r // i)
		r -= 1

def dim(k, r):
	for i in range(1, k + 1):
		c2.append(c2[i - 1] * r // i)
		r -= 1

def fans(k):
	suma = 0
	for i in range(1, k + 1):
		suma += c1[i - 1] * c2[i] * pow(2, i, modu)
	return suma % modu
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	if k > n:
		print(0)
	elif k == n:
		print(2)
	else:
		c1 = [1]
		c2 = [1]
		nc(k, k - 1)
		dim(k, n - k + 1)
		print(fans(k))


import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
modinv_mem = {}

def modinv(n):
	if n not in modinv_mem:
		modinv_mem[n] = pow(n, MOD - 2, MOD)
	return modinv_mem[n]
C_mem = {}

def C(n, k):
	if k == 0:
		return 1
	if (n, k) not in C_mem:
		C_mem[n, k] = n * modinv(k) * C(n - 1, k - 1) % MOD
	return C_mem[n, k]
for i in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	if k > n:
		print(0)
	else:
		for i in range(k):
			ans += C(n - k + 1, i + 1) * C(k - 1, i) * pow(2, i + 1, MOD) % MOD
		print(int(ans % MOD))


import math
global pri
pri = 1000000007

def gcd(n, m):
	if n == 0:
		return m
	else:
		return gcd(m % n, n)

def modinv(n):
	tmp = gcd(n, pri)
	return pow(n, pri - 2, pri)
pri = 1000000007

def cho(n, r):
	if r > n:
		return 0
	elif r == n or r == 0:
		return 1
	else:
		k = n - r
		tmp = 1
		tmp1 = 1
		for i in range(1, r + 1):
			tmp = tmp * (k + i) % pri
			tmp1 = tmp1 * i % pri
		tmp1 = modinv(tmp1)
		tmp = tmp % pri * (tmp1 % pri) % pri
		return tmp % pri
t = input()
t = int(t)
while t:
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	s = 0
	x = n - k + 1
	for i in range(0, k):
		s = s + cho(k - 1, i) % pri * (cho(x + i, k) % pri) % pri
	y = 2 * s % pri
	print(y)
	t = t - 1


import functools
mod = 1000000007

def ncr(n, r):
	if r > n:
		return 0
	else:
		r = min(r, n - r)
		a = functools.reduce(lambda x, y: x * y, range(n, n - r, -1), 1)
		b = functools.reduce(lambda x, y: x * y, range(1, r + 1), 1)
		return a // b
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 0
	for i in range(k):
		m += 2 * ncr(k - 1, i) * ncr(n + 1 + i - k, k) % mod
	print(m % mod)


mod = 10 ** 9 + 7
for i in range(int(input())):
	(a, b) = map(int, input().split())
	if b > a:
		print(0)
	elif b == a:
		print(2)
	else:
		ans = 2 * (a - b + 1)
		comb1 = (a - b + 1) * (a - b) // 2
		comb2 = b - 1
		for j in range(1, min(a - b + 1, b)):
			ans = ans + pow(2, j + 1, mod) * comb1 * comb2
			comb1 = (a - b - j) * comb1 // (j + 2)
			comb2 = (b - j - 1) * comb2 // (j + 1)
		print(ans % mod)


t = int(input())
while t:
	(n, k) = map(int, input().split(' '))
	mod = 10 ** 9 + 7

	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 getpascal(n):
		coff = []
		coff.append(1)
		for i in range(1, n + 1):
			den = modinv(i, mod)
			num = (n - i + 1) % mod
			coff.append(coff[i - 1] * num % mod * den % mod)
			if len(coff) > k:
				break
		return coff
	coef1 = getpascal(k - 1)
	coef2 = getpascal(n - k + 1)
	pow2 = 2
	sum = 0
	for i in range(1, k + 1):
		try:
			sum += pow2 * coef1[i - 1] % mod * coef2[i] % mod
			sum %= mod
			pow2 = pow2 * 2 % mod
		except:
			break
	print(sum)
	t = t - 1


mod = 1000000007

def modular_inverse(value):
	return fast_mod_pow(value, mod - 2)

def fast_mod_pow(a, x):
	value = 1
	while x > 0:
		if x % 2 != 0:
			value = value * a % mod
		a = a * a % mod
		x //= 2
	return value

def modular_biomial_coffiecient(n, r):
	deno = 1
	for i in range(1, r + 1):
		deno = deno * i % mod
	nume = 1
	for i in range(r):
		nume = nume * (n - i) % mod
	return nume * modular_inverse(deno) % mod
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ans = 0
	if k > n:
		print(0)
	else:
		for i in range(k):
			ans = (ans + 2 * modular_biomial_coffiecient(k - 1, i) * modular_biomial_coffiecient(n + 1 + i - k, k)) % mod
		print(ans)


from functools import reduce as rd
import operator as optr
inp = lambda : map(int, input().split())

def Combination(n, r):
	r = min(r, n - r)
	numerator = rd(optr.mul, range(n, n - r, -1), 1)
	denominator = rd(optr.mul, range(1, r + 1), 1)
	return numerator // denominator
mod = 10 ** 9 + 7
test = int(input())
for __ in range(test):
	(n, k) = inp()
	result = 0
	if n >= k:
		if n % 2 == 0 and k <= n // 2 or (n % 2 != 0 and k <= n // 2 + 1):
			for i in range(1, k + 1):
				result += 2 ** i % mod * Combination(k - 1, i - 1) % mod * Combination(n - k + 1, i) % (10 ** 9 + 7) % mod
		else:
			cnt = 0
			for i in range(1, k + 1):
				result += 2 ** i % mod * Combination(k - 1, i - 1) % mod * Combination(n - k + 1, i) % (10 ** 9 + 7) % mod
				cnt += 1
				if cnt == n - k + 1:
					break
		print(result % mod)
	else:
		print(0)


import functools
import operator as op

def ncr(n, r):
	r = min(r, n - r)
	numer = functools.reduce(op.mul, range(n, n - r, -1), 1)
	deno = functools.reduce(op.mul, range(1, r + 1), 1)
	return numer // deno
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	mod = 10 ** 9 + 7
	if n < k:
		ans = 0
	elif n % 2 == 0:
		if k <= n // 2:
			for i in range(1, k + 1):
				ans += 2 ** i % mod * ncr(k - 1, i - 1) % mod * ncr(n - k + 1, i) % (10 ** 9 + 7) % mod
		else:
			cnt = 0
			for i in range(1, k + 1):
				ans += 2 ** i % mod * ncr(k - 1, i - 1) % mod * ncr(n - k + 1, i) % (10 ** 9 + 7) % mod
				cnt += 1
				if cnt == n - k + 1:
					break
	elif k <= n // 2 + 1:
		for i in range(1, k + 1):
			ans += 2 ** i % mod * ncr(k - 1, i - 1) % mod * ncr(n - k + 1, i) % (10 ** 9 + 7) % mod
	else:
		cnt = 0
		for i in range(1, k + 1):
			ans += 2 ** i % mod * ncr(k - 1, i - 1) % mod * ncr(n - k + 1, i) % (10 ** 9 + 7) % mod
			cnt += 1
			if cnt == n - k + 1:
				break
	print(ans % mod)


from operator import mul
from itertools import *
from functools import *
m = 10 ** 9 + 7

def nCr(n, r):
	if r > n - r:
		r = n - r
	return reduce(mul, range(n - r + 1, n + 1), 1) // reduce(mul, range(1, r + 1), 1) % m

def find(n, k):
	if k == 0:
		return 1
	elif k > n:
		return 0
	elif k == n:
		return 2
	else:
		n += 1
		ans = 0
		for i in range(1, min(n - k, k) + 1):
			ans = (ans + pow(2, i, m) * nCr(k - 1, i - 1) * nCr(n - k, i) % m) % m
		return ans
T = int(input())
for testCase in range(T):
	(N, K) = list(map(int, input().split()))
	print(find(N, K))


def replace(n, k):
	d = [0 for _ in range(k + 1)]
	d[0] = 1
	d[1] = 2 * (n - k + 1)
	for i in range(2, k + 1):
		d[i] = (2 * (n - k + 1) * d[i - 1] + (i - 2) * d[i - 2]) // i
	return d[k]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ways = 0
	if k > n:
		print(0)
		continue
	print(replace(n, k) % 1000000007)


mod = 1000000007

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

def checkbin(n, k):
	if k > n:
		return 0
	elif k == n:
		return 1
	else:
		num = 1
		for i in range(k):
			num = num % mod * ((n - i) % mod) % mod
		denom = 1
		for i in range(1, k + 1):
			denom = denom % mod * (i % mod) % mod
		return num % mod * (modinv(denom, mod) % mod) % mod

def solve(n, k):
	answer = 0
	for i in range(n + 1):
		answer = (answer % mod + checkbin(n, i) % mod * (checkbin(k, i) % mod) % mod * (pow(2, i, mod) % mod) % mod) % mod
	return answer
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	answer = 0
	if k == 1:
		answer = 2 % mod * (n % mod) % mod
	elif n == k:
		answer = 2
	elif n > k:
		answer = (solve(k, n - k) % mod + solve(k - 1, n - k) % mod) % mod
	print(answer)
	t = t - 1


import sys
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

def nCr(n, r):
	if r == 0:
		return 1
	return nCr(n, r - 1) * (n - r + 1) // r
a = int(input())
for i in range(a):
	b = [int(i) for i in input().split()]
	n = b[0]
	k = b[1]
	s = 0
	if k <= n:
		for r in range(1, k + 1):
			s = s + int(2 ** r * nCr(k - 1, r - 1) * nCr(n - k + 1, r))
			s = s % mod
		s = s % mod
	print(s)


(a, b, mod) = ([], [], pow(10, 9) + 7)

def funca(k, w):
	for i in range(1, k):
		a.append(a[i - 1] * w // i)
		w -= 1

def funcb(k, w):
	for i in range(1, k + 1):
		b.append(b[i - 1] * w // i)
		w -= 1

def answer(k):
	ans = 0
	for i in range(1, k + 1):
		ans += a[i - 1] * b[i] * pow(2, i, mod)
	return ans % mod
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
	elif k == n:
		print(2)
	else:
		(a, b) = ([1], [1])
		funca(k, k - 1)
		funcb(k, n - k + 1)
		print(answer(k))


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

def powerMod(n, k, m):
	if k == 0:
		return 1
	if k == 1:
		return n % m
	pw = powerMod(n, k // 2, m)
	if k % 2 == 0:
		return pw * pw % m
	else:
		return pw * pw * n % m

def inverseMod(n, m):
	return powerMod(n, m - 2, m)

def choiceMod(n, k, m):
	nprod = 1
	kprod = 1
	invrm1f = 1
	invrf = 1
	rf = 1
	power2 = 1
	result = 0
	for r in range(1, k + 1):
		rf = rf * r % m
		invrm1f = invrf
		invrf = inverseMod(rf, m)
		nprod = nprod * (n - r + 2) % m
		power2 = power2 * 2 % m
		result = (result + nprod * invrf * power2 * kprod * invrm1f) % m
		kprod = kprod * (k - r) % m
	return result
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	if k == 0:
		print(1)
	elif k > n:
		print(0)
	elif k == n:
		print(2)
	else:
		print(choiceMod(n - k, k, M))


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
for it in range(t):
	(n, k) = [int(x) for x in input().split()]
	ans = 0
	MOD = 1000000007
	n += 1
	if n >= k:
		for i in range(k):
			mul = ncr(n - k, i + 1, MOD) * 1 % MOD
			mul = mul * ncr(k - 1, i, MOD) % MOD
			mul = mul * pow(2, i + 1, MOD) % MOD
			ans = (ans + mul) % MOD
	print(ans)


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(n, k) = [int(x) for x in stdin.readline().split()]
	if k > n:
		print(0)
	elif n == k:
		print(2)
	elif k == 1:
		print(2 * n % (10 ** 9 + 7))
	else:
		x = 1
		c1 = 2 * (n - k + 1)
		f = min(k - 1, n - k)
		c = 4
		n1 = (n - k + 1) * (n - k) // 2
		n2 = k - 1
		flag = 1
		while flag:
			a = c * n1 * n2
			c1 += a
			n1 = (n - k - x) * n1 // (x + 2)
			n2 = n2 * (k - x - 1) // (x + 1)
			c *= 2
			x += 1
			f -= 1
			if f > 0:
				continue
			else:
				flag = 0
		print(c1 % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	ans = 0
	if k > n:
		print(0)
	else:
		term = (n - k + 1) * 2
		for r in range(1, k + 1):
			ans += term
			term = term * 2 * (k - r) * (n - k + 1 - r) // (r * (r + 1))
		print(int(ans) % (10 ** 9 + 7))


mod = int(1000000000.0) + 7

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

def solve(n, k):
	ans = 0
	ra = min(k, n - k + 1)
	aux1 = genAux1(k - 1, ra - 1)
	aux2 = genAux1(n - k + 1, ra)
	prev = 1
	for r in range(1, ra + 1):
		prev = prev * 2
		ans += prev % mod * aux1[r - 1] * aux2[r]
	print(ans % mod)

def genAux1(n, k):
	result = [1] * (k + 1)
	for r in range(1, k + 1):
		result[r] = result[r - 1] * (n - r + 1) * inv(r) % mod
	return result
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if k > n:
		print(0)
	else:
		solve(n, k)


import sys
sys.setrecursionlimit(10 ** 9)
M = 10 ** 9 + 7
d = {}

def ncr(n, r):
	if r == 0:
		return 1
	elif n < r:
		return 0
	elif (n, r) in d:
		return d[n, r]
	else:
		d[n, r] = (n - r + 1) * ncr(n, r - 1) // r
		return d[n, r]

def solve(n, k):
	if k == 0:
		return 1
	ans = 0
	for r in range(1, k + 1):
		ans = (ans % M + 2 ** r % M * (ncr(k - 1, r - 1) % M) % M * (ncr(n - k + 1, r) % M) % M) % M
	return ans
for _ in range(int(input())):
	(n, k) = (int(s) for s in input().split())
	if k > n:
		print(0)
	else:
		print(solve(n, k))


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
Q = 10 ** 9 + 7
ncr = defaultdict(int)

def choose(n, k):
	if k == 0 or k == n:
		return 1
	elif k == 1 or k == n - 1:
		return n
	elif (n, k) in ncr:
		return ncr[n, k]
	else:
		a = choose(n, k - 1) * (n - k + 1) // k
		ncr[n, k] = a
		return a

def solve(n, r):
	sm = 0
	if r > n:
		return 0
	for i in range(1, r + 1):
		sm = (sm % Q + 2 ** i % Q * (choose(r - 1, i - 1) % Q) % Q * (choose(n - r + 1, i) % Q) % Q) % Q
	if r == 0:
		return 1
	return sm
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	print(solve(n, k))


inf = 1000000007
pow2 = list()
pow2.append(1)
for i in range(1, 1100):
	pow2.append(pow2[i - 1] * 2 % inf)

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
for x in range(t):
	(n, k) = [int(i) for i in input().strip().split(' ')]
	ans = 0
	val = 0
	for j in range(1, k + 1):
		val = ncr(n - k + 1, j, inf) * ncr(k - 1, j - 1, inf) % inf
		val = val * pow2[j] % inf
		ans = (ans + val) % inf
	ans = ans % inf
	if n < k:
		ans = 0
	print(int(ans))


modulo = 1000000007
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k > n:
		print('0')
		continue
	iterations = min(k - 1, n - k)
	answer = n - k + 1 << 1
	c = 4
	temp2 = (n - k + 1) * (n - k) // 2
	temp1 = k - 1
	r = 1
	for i in range(iterations):
		prod = c * temp1 * temp2
		answer += prod
		c = c << 1
		temp1 = (k - r - 1) * temp1 // (r + 1)
		temp2 = (n - k - r) * temp2 // (r + 2)
		r += 1
		iterations -= 1
	print(answer % modulo)


import sys
from collections import defaultdict
dp1 = defaultdict(int)
dp2 = defaultdict(int)
sys.setrecursionlimit(10 ** 9)
m = 10 ** 9 + 7

def ncr(n, r):
	if r == 0:
		return 1
	elif r == 1:
		return n
	elif (n, r) in dp1:
		return dp1[n, r]
	else:
		p = ncr(n, r - 1) * (n - r + 1) // r
		dp1[n, r] = p
		return p

def fun(n, k):
	if k > n:
		return 0
	elif k == 0:
		return 1
	elif k == n:
		return 2
	else:
		r1 = 0
		for i in range(1, k + 1):
			r1 += 2 ** i % m * (ncr(k - 1, i - 1) % m) % m * (ncr(n - k + 1, i) % m) % m
		return r1 % m
for i in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	print(fun(n, k))


def ncr(n, r):
	if n < r:
		return 0
	num = den = 1
	for i in range(1, r + 1):
		num = num * (n - i + 1) % mod
		den = den * i % mod
	return num * pow(den, mod - 2, mod) % mod
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for ki in range(k + 1, 1, -1):
		ans = (ans + ncr(n - k + 1, ki - 1) * pow(2, ki - 1, mod) % mod * ncr(k - 1, ki - 2)) % mod
	print(ans)


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

def solve(n, k):
	n += 1
	res = 0
	for i in range(k + 1):
		res += ncr(k - 1, i) * ncr(n - k, i + 1) * 2 ** (i + 1)
	return res % 1000000007
t = int(input())
for i in range(t):
	(n, r) = input().split()
	n = int(n)
	r = int(r)
	print(int(solve(n, r)))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	if k > n:
		print('0')
		continue
	x = 1
	count = 2 * (n - k + 1)
	f = min(k - 1, n - k)
	c = 4
	n1 = (n - k + 1) * (n - k) // 2
	n2 = k - 1
	d2 = 1
	while f > 0:
		a = c * n1 * n2
		count += a
		n1 = (n - k - x) * n1 // (x + 2)
		n2 = n2 * (k - x - 1) // (x + 1)
		c = c * 2
		x += 1
		f -= 1
	print(count % 1000000007)


m = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = [int(n) for n in input().split()]
	if n == k:
		print(2)
		continue
	if k > n:
		print(0)
		continue
	ans = 0
	k1 = k - 1
	n1 = n - k + 1
	a = [1]
	for i in range(1, k):
		p = a[i - 1] * k1 // i
		a.append(p)
		k1 = k1 - 1
	b = [1]
	for i in range(1, k + 1):
		p = b[i - 1] * n1 // i
		b.append(p)
		n1 = n1 - 1
	for i in range(1, k + 1):
		ans = ans + a[i - 1] * b[i] * pow(2, i, m)
		ans = ans % m
	print(ans)


import math
from sys import stdin, stdout
m = int(1000000000.0 + 7)

def ncr_fun_mod_m(n, r):
	c = [0 for i in range(r + 1)]
	c[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, r), 0, -1):
			c[j] = (c[j] + c[j - 1]) % m
	return c[r]
for _ in range(int(input())):
	(n, k) = [int(n) for n in input().split()]
	if n == k:
		print(2)
		continue
	if k > n:
		print(0)
		continue
	ans = 0
	k1 = k - 1
	n1 = n - k + 1
	a = [1]
	for i in range(1, k):
		p = a[i - 1] * k1 // i
		a.append(p)
		k1 = k1 - 1
	b = [1]
	for i in range(1, k + 1):
		p = b[i - 1] * n1 // i
		b.append(p)
		n1 = n1 - 1
	for i in range(1, k + 1):
		ans = ans + a[i - 1] * b[i] * pow(2, i, m)
		ans = ans % m
	print(ans)


mod = 1000000007

def powermod(base, exp, mod):
	base %= mod
	result = 1
	while exp > 0:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result

def inversemod(a, mod):
	return powermod(a, mod - 2, mod)

def binomial_nCr(n, k, mod):
	if k > n or n < 0 or k < 0:
		return 0
	else:
		num = 1
		for i in range(k):
			num = num * (n - i) % mod
		den = 1
		for i in range(1, k + 1):
			den = den * i % mod
		return num * inversemod(den, mod) % mod

def comb_fn(N, k):
	if k > N or N < 0 or k < 0:
		return 0
	else:
		top = N
		comb_val = 1
		while top > N - k:
			comb_val *= top % mod
			top -= 1
		n = 1
		while n < k + 1:
			comb_val //= n % mod
			n += 1
		return comb_val

def comb_fn1(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i) / (i + 1) % mod
	return int(res)
tc = int(input())
for i in range(tc):
	(n, k) = [int(x) for x in input().split()]
	opmodbn = 0
	for i in range(0, k + 1):
		opmodbn = (opmodbn + pow(2, i) % mod * binomial_nCr(n - k + 1, i, mod) * binomial_nCr(k - 1, i - 1, mod)) % mod
	print(opmodbn)


mod = 1000000007
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
		continue
	s = 0
	for x in range(1, min(n - k + 1, k) + 1):
		p = 1
		for i in range(x):
			p = p * 2 % mod
		for i in range(1, x + 1):
			p = p * (n - k - x + 1 + i) // i
		p %= mod
		q = 1
		for i in range(1, x):
			q = q * (k - x + i) // i
		q %= mod
		s += p * q % mod
		s %= mod
	print(s)


import math
mod = 1000000007
t = int(input())
powers = []
i = 1
while i <= mod - 2:
	if i & mod - 2:
		powers.append(i)
	i <<= 1

def inv(num):
	tmp = num
	key = 1
	ans = 1
	while key < mod - 2:
		if key in powers:
			ans = ans * tmp % mod
		key *= 2
		tmp = tmp * tmp % mod
	return ans

def comb(a, b):
	if a < 0 or b < 0 or a < b:
		return 0
	ans = 1
	for i in range(max(a - b + 1, b + 1), a + 1):
		ans *= i % mod
	b = math.factorial(min(b, a - b)) % mod
	return ans * inv(b)
for i in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	for j in range(1, k + 1):
		ans += pow(2, j) * comb(k - 1, j - 1) * (comb(n - k - 1, j - 2) + 2 * comb(n - k - 1, j - 1) + comb(n - k - 1, j))
		ans %= mod
	if n == k:
		ans = 2
	print(ans)


from sys import stdin, stdout
cin = stdin.readline
cout = stdout.write

def Soeras(n):
	emirp = [True for i in range(n + 1)]
	j = 2
	while j * j <= n:
		if emirp[p] == True:
			for i in range(j * 2, n + 1, j):
				emirp[i] = False
		j += 1
mod = int(1000000000.0 + 7)

def retmod(num):
	return num % mod

def spi():
	return cin().split()

def ncrmetferm(n, r, p):
	upr = 1
	low = 1
	for i in range(r):
		upr = upr * (n - i)
		upr = upr % p
		low = low * (i + 1)
		low = low % p
	pwval = pow(low, p - 2, p)
	retval = upr * pwval % p
	return retval

def compt(minima, n, k):
	calc = 0
	for i in range(1, mini):
		ncrval1 = ncrmetferm(k - 1, i - 1, mod) % mod
		ncrval2 = ncrmetferm(n + 1 - k, i, mod)
		calc = (calc % mod + ncrval1 * ncrval2 % mod % mod * pow(2, i, mod) % mod) % mod
	return calc
t = int(cin())
for cases in range(t):
	(n, k) = list(map(int, spi()))
	mini = min(n + 1 - k, k) + 1
	res = compt(mini, n, k)
	retmod(res)
	print(res)


from sys import stdin, stdout
cin = stdin.readline
cout = stdout.write

def ii():
	return int(cin())

def li():
	return list(map(int, cin().split()))
mod = int(1000000000.0 + 7)

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
for _ in range(ii()):
	(n, k) = li()
	s = 0
	for i in range(1, min(n + 1 - k, k) + 1):
		s = (s % mod + ncr(k - 1, i - 1, mod) % mod * ncr(n + 1 - k, i, mod) % mod % mod * pow(2, i, mod) % mod) % mod
	s %= mod
	print(s)


p = 1000000007

def binomial(n, r):
	numerator = denominator = 1
	for i in range(r):
		numerator = numerator * (n - i) % p
		denominator = denominator * (i + 1) % p
	return numerator * pow(denominator, p - 2, p) % p
t = int(input())
while t:
	answer = 0
	inp = list(map(int, input().split()))
	n = inp[0]
	r = inp[1]
	if r <= n / 2:
		end = r
	else:
		end = n - r + 1
	for i in range(0, end):
		answer += binomial(n - r + 1, i + 1) * binomial(r - 1, i) * ((1 << i + 1) % p) % p
	print(answer % p)
	t -= 1


import math
T = int(input())

def ncr(n, k):
	num = 1
	denom = 1
	for i in range(1, k + 1):
		num = num * (n - (k - i))
		denom = denom * i
	return num // denom

def bricks(N, K):
	s = 0
	for p in range(1, min(K, N - K + 1) + 1):
		s += 2 ** p * ncr(N - K + 1, p) * ncr(K - 1, p - 1) % (10 ** 9 + 7)
	return s % (10 ** 9 + 7)
for i in range(T):
	(n, k) = map(int, input().split())
	print(bricks(n, k))


import math

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
while t > 0:
	(n, r) = map(int, input().split())
	n = n + 1
	if n - r > r:
		k = r
	else:
		k = n - r
	sum = 0
	for i in range(1, k + 1):
		a = ncr(r - 1, i - 1, 1000000007)
		b = ncr(n - r, i, 1000000007)
		c = 2 ** i % 1000000007
		s = a * b * c % 1000000007
		sum = sum % 1000000007 + s
	print(sum % 1000000007)
	t = t - 1


mod = 7 + 10 ** 9
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split(' ')]
	(a, b) = ([1], [1])
	if k > n:
		print(0)
		continue
	for i in range(1, k + 1):
		x = a[-1] * (n - k + 1 - (i - 1))
		bb = i
		x = x * pow(bb, mod - 2, mod) % mod
		a.append(x)
	for i in range(1, k + 1):
		x = b[-1] * (k - i)
		bb = i
		x = x * pow(bb, mod - 2, mod) % mod
		b.append(x)
	ans = 0
	for i in range(k):
		ans = (ans + a[i + 1] * b[i] * (1 << i + 1)) % mod
	print(ans)


T = int(input())
mod = 1000000007
for t in range(T):
	(N, R) = map(int, input().split())
	if R > N:
		print(0)
		continue
	if R == 1:
		print(2 * N % mod)
		continue
	N += 1
	ans = num = (N - R) * 2
	den = 1
	for i in range(2, min(N - R, R) + 1):
		num *= (R + 1 - i) * (N - R + 1 - i) * 2
		den *= (i - 1) * i
		ans += num // den
	print(ans % mod)


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
for i in range(1, t + 1):
	(n, r) = map(int, input().split())
	beauty = 0
	n = n + 1
	if n - r > r:
		k = r
	else:
		k = n - r
	for j in range(1, k + 1):
		pehela = ncr(r - 1, j - 1, 1000000007)
		dusra = ncr(n - r, j, 1000000007)
		teesra = 2 ** j % 1000000007
		chautha = pehela * dusra * teesra % 1000000007
		beauty = beauty % 1000000007 + chautha
	print(beauty % 1000000007)


mod = pow(10, 9) + 7
tc = int(input())
for _ in range(tc):
	p1 = [1]
	(n, k) = [int(i) for i in input().split(' ')]
	if k > n:
		print(0)
	elif k == n:
		print(2)
	else:
		n += 1
		r1 = 1
		for i in range(1, k + 1):
			r1 = r1 * (n - k - i + 1) * pow(i, mod - 2, mod) % mod
			p1.append(r1)
		r2 = 1
		p2 = [1]
		for i in range(1, k):
			r2 = r2 * (k - 1 - i + 1) * pow(i, mod - 2, mod) % mod
			p2.append(r2)
		s = 0
		for i in range(k):
			s += p1[i + 1] * p2[i] % mod * pow(2, i + 1, mod) % mod
		print(s % mod)


import math
for _ in range(int(input())):
	mod = 1000000007
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
	else:
		x = n - k
		dp = [0] * (k + 1)
		dp[0] = 1
		dp[1] = 2 * x + 2
		for i in range(2, k + 1):
			dp[i] = (dp[1] * dp[i - 1] + (i - 2) * dp[i - 2]) * pow(i, mod - 2, mod)
		print(dp[k] % mod)


from sys import stdin
xrange = range
MOD = 10 ** 9 + 7

def kfact(k):
	kf = [1] * (k + 1)
	f = 1
	for i in xrange(2, k + 1):
		f = f * i % MOD
		kf[i] = f
	return kf

def rkfact(n, k):
	k = min(n, k)
	rkf = [1] * (k + 1)
	f = 1
	for i in xrange(1, k + 1):
		f = f * (n - i + 1) % MOD
		rkf[i] = f
	return rkf

def bricks(n, k):
	kf = kfact(k)
	s = min(k, n - k + 1)
	rkf = rkfact(n - k + 1, s)
	r = 0
	for i in xrange(1, s + 1):
		nom = kf[k - 1]
		den = kf[i - 1] * kf[k - i] % MOD
		nom = nom * pow(den, MOD - 2, MOD) % MOD
		nom = nom * pow(2, i, MOD) % MOD
		nom = nom * rkf[i] * pow(kf[i], MOD - 2, MOD) % MOD
		r = (r + nom) % MOD
	return r

def main():
	readl = stdin.readline
	for __ in xrange(int(readl())):
		(n, k) = map(int, readl().split())
		if k > n:
			print(0)
		else:
			print(bricks(n, k))
main()


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
mod = 1000000007
for j in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	for i in range(1, min(n - k + 2, k + 1)):
		ans += pow(2, i, mod) * ncr(k - 1, i - 1, mod) * ncr(n - k + 1, i, mod)
		ans %= mod
	print(int((ans + mod) % mod))


mod = 1000000007

def MODPow(base, exp, mod):
	base %= mod
	result = 1
	while exp > 0:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result

def MODInverse(a, p):
	return MODPow(a, p - 2, p)

def MODBinomial(n, k, p):
	if k > n or n < 0 or k < 0:
		return 0
	else:
		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) % p

def comb_fn(N, k):
	if k > N or N < 0 or k < 0:
		return 0
	else:
		top = N
		comb_val = 1
		while top > N - k:
			comb_val *= top % mod
			top -= 1
		n = 1
		while n < k + 1:
			comb_val //= n % mod
			n += 1
		return comb_val

def comb_fn1(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i) / (i + 1) % mod
	return int(res)
tc = int(input())
for i in range(tc):
	(n, k) = [int(x) for x in input().split()]
	opmodbn = 0
	for i in range(0, k + 1):
		opmodbn = (opmodbn + pow(2, i) % mod * MODBinomial(n - k + 1, i, mod) * MODBinomial(k - 1, i - 1, mod)) % mod
	print(opmodbn)


import math

def ncr(n, r):
	pro1 = 1
	pro2 = 1
	for i in range(r):
		pro1 *= n - i
		pro2 *= i + 1
	return pro1 // pro2
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = 0
	for p in range(1, min(n - k + 1, k) + 1):
		s += 2 ** p * ncr(n - k + 1, p) * ncr(k - 1, p - 1) % (10 ** 9 + 7)
	print(s % (10 ** 9 + 7))


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

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

def nCr(n, k, p):
	if k < 0:
		return 0
	elif k > n:
		return 0
	else:
		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
x = int(input())
mod = 10 ** 9 + 7
for j in range(x):
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(0, a[1] + 1):
		ans = (ans + power(2, i, mod) * nCr(a[0] - a[1] + 1, i, mod) * nCr(a[1] - 1, i - 1, mod)) % mod
	print(int(ans))


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

def nCr(n, k, p):
	if k > n or n < 0 or k < 0:
		return 0
	else:
		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
tc = int(input())
for i in range(tc):
	(n, k) = [int(x) for x in input().split()]
	ans = 0
	mod = 1000000007
	for i in range(1, k + 1):
		ans = (ans + pow(2, i) * nCr(n - k + 1, i, mod) % mod * nCr(k - 1, i - 1, mod) % mod) % mod
	print(int(ans))


def C(n, r, p):
	if r < 0 or r > n:
		return 0
	if r > n - r:
		r = n - r
	(ans, dans) = (1, 1)
	for i in range(1, r + 1):
		ans = ans * ((n - r + i) % p) % p
		dans = dans * i % p
	ret = ans * pow(dans, p - 2, p) % p
	return ret % p
ts = input()
t = int(ts)
while t:
	(n, k) = map(int, input().split(' '))
	(ans, p) = (0, int(1000000000.0 + 7))
	for i in range(1, k + 1):
		ans = (ans + C(k - 1, i - 1, p) * C(n - k + 1, i, p) % p * pow(2, i, p) % p) % p
	print(ans % p)
	t -= 1


def nCr(n, k):
	if k > n:
		return 0
	mod = 10 ** 9 + 7
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res // (i + 1)
	return res % mod

def ans(n, k):
	ans = 0
	mod = 10 ** 9 + 7
	for i in range(0, k):
		ans += nCr(n - k, i + 1) * nCr(k - 1, i) * 2 ** (i + 1)
	return ans % mod
from sys import stdin, stdout

def main():
	t = int(input())
	mod = 10 ** 9 + 7
	for i in range(0, t):
		z = input()
		z = z.split(' ')
		n = int(z[0])
		k = int(z[1])
		k = ans(n + 1, k)
		stdout.write(str(k % mod))
		stdout.write(str('\n'))
main()


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

def func(n, r):
	sum = 0
	for i in range(0, r):
		sum = (sum + com(n - r, i + 1) * com(r - 1, i) * pow(2, i + 1, 1000000007)) % 1000000007
	return sum
t = int(input())
for i in range(0, t):
	x = input().split(' ')
	n = int(x[0])
	k = int(x[1])
	print(func(n + 1, k))


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num % p * ((n - i) % p) % p
		den = den % p * ((i + 1) % p) % p
	return num % p * pow(den, p - 2, p) % p
t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	x = 0
	if k > n:
		print(0)
	else:
		m = 1000000007
		for i in range(1, k + 1):
			y = pow(2, i, m) * ncr(k - 1, i - 1, m) % m * ncr(n - k + 1, i, m) % m
			x = (x % m + y % m) % m
		print(x)


def binomial(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
m = 10 ** 9 + 7

def T(n, r):
	return int(sum([binomial(r - 1, k - 1) * binomial(n - r, k) * 2 ** k for k in range(min(n - r, r) + 1)]))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	ans = T(n + 1, k)
	print(ans % m)


def ncr(n, k):
	if n < k:
		return 0
	num = 1
	den = 1
	if k > n - k:
		k = n - k
	for i in range(1, k + 1):
		num = num * (n - k + i)
		den = den * i
	ans = num // den
	return ans % 1000000007
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if k > n:
		print('0')
		continue
	ans = 0
	for i in range(k):
		ans = (ans + ncr(n + 1 - k, i + 1) * ncr(k - 1, i) % 1000000007 * 2 ** (i + 1) % 1000000007) % 1000000007
	print(int(ans))


def _C(n, r):
	global f
	if n < 0 or r < 0:
		return 1
	if n < r:
		return 1
	return f[n] // (f[n - r] * f[r])
t = int(input())
global f
f = [1, 1]
for i in range(2, 1001):
	f.append(f[i - 1] * i)
for _ in range(t):
	(n, k) = map(int, input().split())
	times = min(k, (n + 1) // 2)
	s = 0
	two = 2
	upp = n - k + 1
	down = 1
	if n < k:
		print('0')
		continue
	for i in range(1, times + 1):
		s = s + two * _C(k - 1, i - 1) * upp // down
		s = s % 1000000007
		two = two * 2
		upp = upp * (n - k + 1 - i)
		down = down * (i + 1)
	print(s)


p = int(pow(10, 9) + 7)

def modBin(n, k, p):
	nu = 1
	for i in range(0, k):
		nu = nu * (n - i) % p
	de = 1
	for i in range(1, k + 1):
		de = de * i % p
	return nu * pow(de, p - 2, p) % p
for t in range(0, int(input())):
	(n, k) = map(int, input().split(' '))
	n = n + 1
	if k > n:
		print(0)
	else:
		answer = 0
		n = n - k
		y = min(n, k)
		for i in range(0, y + 1):
			f = modBin(k - 1, i - 1, p)
			g = modBin(n, i, p)
			h = int(pow(2, i, p))
			answer = (f % p * g % p * h % p % p + answer % p) % p
		print(answer - 1)


P = int(1000000000.0) + 7

def modpow(a, b):
	ans = 1
	while b:
		if b & 1:
			ans *= a % P
		b >>= 1
		a = a * a % P
	return ans

def modinv(a):
	return modpow(a, P - 2)

def nCr(n, r):
	if r > n - r:
		r = n - r
	ans = 1
	for i in range(1, r + 1):
		ans = ans * (n - r + i) % P
		ans = ans * modinv(i) % P
	return ans % P

def A(n, r):
	ans = 0
	sec = nCr(n, 0)
	fst = 0
	for k in range(min(n, r) + 1):
		(x, y) = (r - 1, k - 1)
		if y < 2:
			fst = nCr(x, y)
		ans = (ans + fst * sec * modpow(2, k)) % P
		fst = fst * (x - y) * modinv(y + 1) % P
		sec = sec * (n - k) * modinv(k + 1) % P
		ans %= P
	return ans % P

def T(m, r):
	ans = A(m - r + 1, r) - 1
	return ans
tc = int(input())
for i in range(tc):
	(n, k) = map(int, input().split())
	if n < k:
		print(0)
	else:
		print(T(n, k))


p = 10 ** 9 + 7

def ncr(n, r):
	if n < r:
		return 0
	ans = 1
	inv = 1
	for i in range(n - r + 1, n + 1):
		ans = ans * i % p
	for i in range(1, r + 1):
		inv = inv * i % p
	inv = pow(inv, p - 2, p)
	return ans * inv % p
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	an = 0
	for j in range(1, k + 1):
		an = (an + pow(2, j, p) * ncr(n - k + 1, j) * ncr(k - 1, j - 1)) % p
	print(an)


import math

def comb(n, r):
	if r > n:
		return 0
	if r == n:
		return 1
	nr = 1
	dr = 1
	if r > n - r:
		r = n - r
	for x in range(n - r + 1, n + 1):
		nr = nr * x
	for x in range(1, r + 1):
		dr = dr * x
	return nr // dr % 1000000007
t = int(input())
for x in range(t):
	(n, k) = [int(x) for x in input().split()]
	if k < 0:
		print('0')
	elif k == 1:
		print(n * 2 % 1000000007)
	else:
		ans = 0
		for i in range(1, k + 1):
			ans = (ans + 2 ** i % 1000000007 * (comb(k - 1, i - 1) % 1000000007) % 1000000007 * (comb(n - k + 1, i) % 1000000007) % 1000000007 % 1000000007) % 1000000007
		print(ans)


mod = int(1000000000.0 + 7)

def find(n, k, mod):
	nu = 1
	de = 1
	for i in range(k):
		nu = nu * (n - i) % mod
		de = de * (i + 1) % mod
	return nu * pow(de, mod - 2, mod) % mod

def pow(q, z, mod):
	res = 1
	q = q % mod
	while z > 0:
		if z & 1 == 1:
			res = res * q % mod
		z = z >> 1
		q = q * q % mod
	return res
for t in range(int(input())):
	(n, k) = map(int, input().split())
	res = 0
	for l in range(1, min(n + 1 - k, k) + 1):
		res = (res % mod + find(k - 1, l - 1, mod) % mod * find(n + 1 - k, l, mod) % mod % mod * pow(2, l, mod) % mod) % mod
	print(res)


p = int(1000000000.0 + 7)

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def calculate(n, r, p):
	numerator = 1
	denominator = 1
	for i in range(r):
		numerator = numerator * (n - i) % p
		denominator = denominator * (i + 1) % p
	return numerator * power(denominator, p - 2, p) % p
for t in range(int(input())):
	(n, r) = map(int, input().split())
	answer = 0
	for k in range(1, min(n + 1 - r, r) + 1):
		answer = (answer % p + calculate(r - 1, k - 1, p) % p * calculate(n + 1 - r, k, p) % p % p * power(2, k, p) % p) % p
	print(answer)


p = int(1000000000.0 + 7)

def calculate(n, r, p):
	numerator = denominator = 1
	for i in range(r):
		numerator = numerator * (n - i) % p
		denominator = denominator * (i + 1) % p
	return numerator * pow(denominator, p - 2, p) % p
for t in range(int(input())):
	(n, r) = map(int, input().split())
	n = n + 1
	answer = 0
	for k in range(1, min(n - r, r) + 1):
		answer = (answer % p + calculate(r - 1, k - 1, p) % p * calculate(n - r, k, p) % p % p * pow(2, k, p) % p) % p
	print(answer)


MOD = int(10 ** 9 + 7)

def power(n, p):
	ans = 1 % MOD
	while p > 0:
		if p % 2 == 1:
			ans = ans * n % MOD
		n = n * n % MOD
		p >>= 1
	return ans

def inver(x):
	return power(x, MOD - 2)
inv = [0] * 1002
for i in range(1, 1002):
	inv[i] = inver(i)

def C(n, k):
	if k < 0 or k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i) % MOD
		res = res * inv[i + 1] % MOD
	return res
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	if N == K:
		print(2)
		continue
	if K > N:
		print(0)
		continue
	res = 0
	for i in range(1, K + 1):
		res = (res + C(N - K + 1, i) * (power(2, i) * C(K - 1, i - 1)) % MOD % MOD) % MOD
	print(res)


def binomial(n, k):
	if 0 <= k <= n:
		(num, den) = (1, 1)
		for t in range(1, min(k, n - k) + 1):
			num *= n
			den *= t
			n -= 1
		return num // den
	else:
		return 0

def T(n, k):
	res = 0
	for i in range(1, k + 1):
		res += 2 ** i * binomial(k - 1, i - 1) * binomial(n - k + 1, i)
	return res % mod

def pascal_style(n, k):
	return (T(n - 2, k - 1) + T(n - 1, k - 1) + T(n - 1, k)) % mod

def hockeystick_style(n, k):
	res = T(n - 1, k)
	for i in range(1, k + 1):
		res += 2 * T(n - i - 1, k - i)
	return res % mod

def solve():
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		if K == 1:
			print(2 * N % mod)
			continue
		if K > N:
			print(0)
			continue
		print(T(N, K))
mod = 10 ** 9 + 7
solve()


import operator as op
import functools

def ncr(n, r):
	r = min(r, n - r)
	numer = functools.reduce(op.mul, range(n, n - r, -1), 1)
	denom = functools.reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
num = 1000000007
var4 = 0
test = input()
test = int(test)
while test > 0:
	ruko1 = 0
	ruko = 0
	test -= 1
	(var1, var2) = [int(x) for x in input().split()]
	var1 += 1
	if var4 == 1:
		var4 = var4 % 2
		var4 = var4 + 3
		var4 = var4 * 2 / 3
	var3 = min(var2, var1 - var2)
	for i in range(1, var3 + 1):
		ruko = ncr(var2 - 1, i - 1) % num * ncr(var1 - var2, i) % num * pow(2, i) % num % num
		ruko1 = (ruko1 % num + ruko % num) % num
	print(ruko1)
	ruko1 = 0


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
tt = int(input())
m = 1000000007
while tt > 0:
	tt = tt - 1
	(nn, k) = input().split()
	nn = int(nn)
	k = int(k)
	nn = nn + 1
	if nn - k <= k:
		na = nn - k
	else:
		na = k
	s = 0
	for x in range(1, na + 1):
		s = (s % m + ncr(k - 1, x - 1, m) % m * ncr(nn - k, x, m) % m * 2 ** x % m % m) % m
	s = s % m
	print(int(s))


MOD = 10 ** 9 + 7
z = []
for i in range(1100):
	z.append(pow(i, MOD - 2, MOD))

def binomial(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i) % MOD
		res = res * z[i + 1] % MOD
	return res

def game(n, k):
	sum = 0
	for i in range(k):
		temp = binomial(n - k, i + 1) * binomial(k - 1, i) % MOD * pow(2, i + 1, MOD) % MOD
		sum = (sum + temp) % MOD
	return sum
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	n = n + 1
	t = game(n, k)
	print(t)


hell = 1000000007

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def C(n, r):
	num = 1
	den = 1
	p = 1
	m = min(n - r, r)
	for i in range(1, m + 1):
		num = (n - i + 1) % hell
		p *= num
		p %= hell
		den = modInverse(i, hell) % hell
		p *= den
		p %= hell
	return p
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = 0
	for i in range(1, min(n - k + 1, k) + 1):
		a = C(n - k + 1, i)
		b = C(k - 1, i - 1)
		c = power(2, i, hell)
		p = a * b % hell
		p *= c
		p %= hell
		s += p
		s %= hell
	print(s)


M = 10 ** 9 + 7

def ip():
	return int(input())

def ipp():
	return map(int, input().split())
dp = []

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def solve2(n, k):
	dp[1] = 2 * (n - k + 1) % M
	dp[2] = 2 * (n - k + 1) * (n - k + 1) % M
	for j in range(3, k + 1):
		p = dp[j - 1]
		q = dp[j - 2]
		r = p * (n - k + 1) * 2 + q * (j - 2)
		r %= M
		r *= modInverse(j, M)
		r %= M
		dp[j] = r
	return dp[k]
for i in range(1023):
	dp.append(-1)
T = ip()
while T != 0:
	(n, k) = ipp()
	if n >= k:
		ans = solve2(n, k)
		ans %= M
		print(ans)
	else:
		print(0)
	T -= 1


MOD = int(1000000000.0 + 7)

def binomial(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 % MOD
	else:
		return 0
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	s = 0
	for r in range(1, k + 1):
		t = pow(2, r, MOD) * binomial(k - 1, r - 1) * binomial(n - k + 1, r)
		t %= MOD
		s += t
		s %= MOD
	print(s)


def calc_ways():
	n = N - (K - 1)
	A = 1
	B = n
	C = 2
	ctr = A * B * C
	for i in range(2, min(n, K) + 1):
		A = A * (K - (i - 1)) // (i - 1)
		B = B * (n - (i - 1)) // i
		C = C * 2 % 1000000007
		ctr = (ctr + A * B * C) % 1000000007
	return str(ctr % 1000000007)
T = int(input())
opList = []
for x in range(T):
	(N, K) = map(int, input().split())
	if 0 in [N, K] or N < K:
		opList.append('0')
	else:
		opList.append(calc_ways())
print('\n'.join(opList))


M = 10 ** 9 + 7

def ip():
	return int(input())

def ipp():
	return map(int, input().split())
dp = []

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def solve(n, k):
	if k == 1:
		dp[1] = 2 * n % M
		return 2 * n % M
	if k == 2:
		x = n - 1
		x = x * x * 2 % M
		dp[2] = x
		return x
	if n == k:
		dp[k] = 2
		return 2
	if dp[k - 1] == -1:
		p = solve(n - 1, k - 1)
	else:
		p = dp[k - 1]
	if dp[k - 2] == -1:
		q = solve(n - 2, k - 2)
	else:
		q = dp[k - 2]
	r = p * (n - k + 1) * 2 + q * (k - 2)
	r %= M
	r *= modInverse(k, M)
	r %= M
	dp[k] = r
	return r
for i in range(1023):
	dp.append(-1)
_ = ip()
while _ != 0:
	i = 0
	for i in range(1008):
		dp[i] = -1
	(n, k) = ipp()
	if k == 1000:
		ans1 = solve(n - 1, k - 1)
		ans2 = solve(n - 2, k - 2)
		ans3 = (n - k + 1) * ans1 * 2 + (k - 2) * ans2
		ans3 *= modInverse(k, M)
		ans3 %= M
		print(ans3)
	elif n > k:
		ans = solve(n, k)
		ans %= M
		print(ans)
	elif n == k:
		print(2)
	else:
		print(0)
	_ -= 1


MOD = 1000000007

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def modInverse(a, m):
	return power(a, m - 2, m)

def ncr(n, r):
	if r > n:
		return 0
	if r == n or n == 0:
		return 1
	num = den = 1
	for i in range(r):
		num = num * (n - i) % MOD
		den = den * (i + 1) % MOD
	return num * power(den, MOD - 2, MOD) % MOD
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k > n or k == 0:
		print(0)
	elif k == n:
		print(2)
	else:
		ans = 0
		for i in range(1, k + 1):
			ans = (ans + power(2, i, MOD) % MOD * (ncr(n - k + 1, i) % MOD * ncr(k - 1, i - 1) % MOD) % MOD) % MOD
		print(ans)


M = 10 ** 9 + 7

def ip():
	return int(input())

def ipp():
	return map(int, input().split())

def sar():
	return list(ipp())
dp = []

def solve(n, k):
	if k == 1:
		return 2 * n
	if k == 2:
		x = n - 1
		x = x * x * 2
		return x
	if n == k:
		return 2
	if dp[k] != -1:
		return dp[k]
	p = solve(n - 1, k - 1)
	q = solve(n - 2, k - 2)
	r = p * (n - k + 1) * 2
	r += q * (k - 2)
	r //= k
	dp[k] = r
	return r
for i in range(100023):
	dp.append(-1)
t = ip()
while t != 0:
	i = 0
	for i in range(100008):
		dp[i] = -1
	(n, k) = ipp()
	if k == 1000:
		ans1 = solve(n - 1, k - 1)
		ans2 = solve(n - 2, k - 2)
		ans3 = (n - k + 1) * ans1 * 2
		ans3 += (k - 2) * ans2
		ans3 //= k
		ans3 %= M
		print(ans3)
	elif n > k:
		ans = solve(n, k)
		ans %= M
		print(ans)
	elif n == k:
		print(2)
	else:
		print(0)
	t -= 1


import math as ma
import sys
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

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

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def num():
	return map(int, input().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
md = [0] * 1100
for i in range(1100):
	md[i] = pow(i, 1000000005, 1000000007)

def binomial(n, k):
	if n < k:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i) % 1000000007
		res = res * md[i + 1] % 1000000007
	return res
mm = 1000000007
t = nu()
for it in range(t):
	(n, k) = num()
	z = n + 1
	ss = 0
	if k > n:
		print(0)
		continue
	pp = [1] * (k + 1)
	for i in range(1, k + 1):
		pp[i] = pp[i - 1] * 2 % mm
	for i in range(0, k):
		ss = (ss + binomial(z - k, i + 1) * binomial(k - 1, i) % mm * pp[i + 1] % mm) % mm
	print(ss % mm)


from sys import stdin

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

def modinv(a, m):
	(g, x, y) = xgcd(a, m)
	if g != 1:
		raise Exception('No modular inverse')
	return x % m
p = 10 ** 9 + 7

def read():
	t = int(stdin.readline().strip())
	cases = []
	for _ in range(t):
		cases.append(list(map(int, stdin.readline().strip().split())))
	return (t, cases)

def solve(n, k):
	if k > n:
		return 0
	m = n - k + 1
	r = 0
	t = 1
	for l in range(min(k, m)):
		t = t * 2 * (m - l) * modinv(l + 1, p) % p
		if l > 0:
			t = t * (k - l) * modinv(l, p) % p
		r = (r + t) % p
	return r
(t, cases) = read()
for (n, k) in cases:
	print(solve(n, k))


mod = 10 ** 9 + 7

def C(n, k):
	if k > n:
		return 0
	elif k == n or k == 0:
		return 1
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res *= n - i
		res //= i + 1
	return res
for t in range(int(input())):
	(N, K) = map(int, input().split())
	ans = 0
	for r in range(1, K + 1):
		ans += pow(2, r) * C(K - 1, r - 1) * C(N - K + 1, r)
	print(ans % mod)


import math
p = 1000000007

def calcnCrMODp(n, r):
	if r < 0:
		return 0
	if n < r:
		return 0
	if r > int(n / 2):
		r = n - r
	val1 = 1
	val2 = 1
	for i in range(r):
		val1 = val1 % p * (n - i) % p % p
		val2 = val2 % p * (i + 1) % p % p
	val2 = val2 % p
	mod_list = [val2]
	b_pow = 2
	log2_b_pow = 1
	while b_pow <= p - 2:
		val2 = val2 % p * (val2 % p) % p
		mod_list.append(val2)
		b_pow = b_pow * 2
		log2_b_pow += 1
	b_pow = int(b_pow / 2)
	log2_b_pow = log2_b_pow - 1
	ans = mod_list[-1]
	rem_pow = p - 2 - b_pow
	while rem_pow > 0:
		b_pow = int(b_pow / 2)
		log2_b_pow -= 1
		if b_pow <= rem_pow:
			rem_pow -= b_pow
			ans = ans % p * mod_list[log2_b_pow] % p % p
	return ans % p * (val1 % p) % p

def mod_pow(a, n):
	val2 = a % p
	mod_list = [val2]
	b_pow = 2
	log2_b_pow = 1
	while b_pow <= n:
		val2 = val2 % p * (val2 % p) % p
		mod_list.append(val2)
		b_pow = b_pow * 2
		log2_b_pow += 1
	b_pow = int(b_pow / 2)
	log2_b_pow = log2_b_pow - 1
	ans = mod_list[-1]
	rem_pow = n - b_pow
	while rem_pow > 0:
		b_pow = int(b_pow / 2)
		log2_b_pow -= 1
		if b_pow <= rem_pow:
			rem_pow -= b_pow
			ans = ans % p * (mod_list[log2_b_pow] % p) % p
	return ans
T = int(input())
for i in range(T):
	_input = input().split()
	N = int(_input[0])
	K = int(_input[1])
	sum_ = 0
	for r in range(K + 1):
		sum_ = (sum_ % p + mod_pow(2, r) * calcnCrMODp(K - 1, r - 1) * calcnCrMODp(N - K + 1, r) % p) % p
	print(sum_)


m = 1000000007

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	return p if y % 2 == 0 else x * p % m

def power2(l):
	ret = 1
	for i in range(l):
		ret = ret % m * 2 % m
	return ret
t = input()
t = int(t)
while t > 0:
	(a, b) = input().split()
	a = int(a)
	b = int(b)

	def T(n, r):
		xx = min(n - r, r) + 1
		fact1 = []
		fact2 = []
		fact1.append(1)
		fact1.append((r - 1) % m)
		fact2.append(1)
		fact2.append((n - r) % m)
		upper1 = r - 1
		upper2 = n - r
		lower = 1
		i1 = r - 2
		i2 = n - r - 1
		j = 2
		x = 0
		for x in range(2, xx + 1):
			upper1 = upper1 % m * (i1 % m) % m
			upper2 = upper2 % m * (i2 % m) % m
			lower = lower % m * (j % m) % m
			fact1.append(upper1 % m * (power(lower, m - 2, m) % m) % m)
			fact2.append(upper2 % m * (power(lower, m - 2, m) % m) % m)
			i1 -= 1
			i2 -= 1
			j += 1
		fact1.append(0)
		fact2.append(0)
		sum = 0
		for k in range(xx):
			sum = (sum % m + fact1[k - 1] * fact2[k] * power2(k) % m) % m
		return sum
	print(T(a + 1, b) % m)
	t -= 1


MOD = 10 ** 9 + 7

def inverse(n):
	(a, b, c, d) = (1, 0, 0, 1)
	(l, r) = (MOD, n)
	while r != 0:
		(a, b, c, d) = (c, d, a - l // r * c, b - l // r * d)
		(l, r) = (r, l % r)
	return b % MOD
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	answer = 0
	binom1 = 1
	binom2 = N - K + 1
	for m in range(1, min(K, N - K + 1) + 1):
		answer = (answer + pow(2, m, MOD) * binom1 * binom2) % MOD
		binom1 = binom1 * (K - m) * inverse(m) % MOD
		binom2 = binom2 * inverse(m + 1) * (N - m - K + 1) % MOD
	print(answer)


def ip():
	return int(input())

def ipp():
	return map(int, input().split())

def sar():
	return list(ipp())

def pars(a):
	print(' '.join(list(map(str, a))))
	print('\r')

def parl(a):
	print('\r'.join(list(map(str, a))))
	print('\r')
m = 1000000007

def ncr(n, r):
	nr = 1
	dr = 1
	for i in range(r):
		nr = nr * (n - i) % m
		dr = dr * (i + 1) % m
	return nr * pow(dr, m - 2, m) % m
T = 1
T = int(input().strip())
for _ in range(T):
	(n, k) = ipp()
	ans = 0
	if k == n:
		print(2)
	elif k > n:
		print(0)
	else:
		for i in range(1, k + 1):
			ans = (ans % m + pow(2, i, m) * (ncr(k - 1, i - 1) * ncr(n - k + 1, i) % m) % m) % m
		print(ans % m)


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
while t != 0:
	(N, K) = map(int, input().split())
	if K > N:
		print(0)
	else:
		ans = 0
		m = 10 ** 9 + 7
		for r in range(1, K + 1):
			ans = (ans + pow(2, r, m) * ncr(K - 1, r - 1, m) % m * ncr(N - K + 1, r, m) % m) % m
		print(ans)
	t = t - 1


from functools import lru_cache
from sys import setrecursionlimit
setrecursionlimit(1000000)
mod = 1000000007

def addR(a, b):
	return (a % mod + b % mod) % mod

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

@lru_cache(maxsize=None)
def combi(n, r):
	if n < 0 or r < 0:
		return 0
	if r == 0:
		return 1
	if n == 0:
		return 0
	ans = 1
	r = max(r, n - r)
	m = n
	while m >= r + 1:
		ans = mulR(ans, m)
		m -= 1
	d = n - r
	while d > 0:
		ans = mulR(ans, poww(d, mod - 2))
		d -= 1
	return ans

@lru_cache(maxsize=None)
def poww(z, l):
	if l == 1:
		return z
	if l == 0:
		return 1
	x = poww(z, int(l / 2))
	y = poww(z, l % 2)
	return mulR(mulR(x, x), y)

def fff(n, k):
	a = n - k + 1
	b = k
	i = 1
	ans = 0
	while i <= min(a, b):
		compo1 = poww(2, i)
		compo2 = combi(a, i)
		compo3 = combi(b - 1, i - 1)
		ans = addR(ans, mulR(mulR(compo1, compo2), compo3))
		i += 1
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	print(fff(n, k))