Consider a set, $\mbox{S}$, consisting of $\boldsymbol{\mbox{k}}$ integers. The set is beautiful if at least one of the following conditions holds true for every $x\in S$:

$x-1\in S$
$x+1\in S$

For example, $S=\{1,2,50,51\}$ is beautiful but $S=\{1,5,9\}$ is not beautiful. Given two integers, $n$ and $\boldsymbol{\mbox{k}}$, can you find the number of different $\boldsymbol{\mbox{k}}$-element beautiful sets you can create using integers $\in[1,n]$?

Perform $\textit{q}$ queries where each query $\boldsymbol{i}$ consists of some $n_i$ and $k_i$. For each query:

Find the number of different beautiful sets having exactly $\boldsymbol{\mbox{k}}$ elements that can be generated using integers in the inclusive range from $1$ to $n$. 
Print the number of beautiful sets, modulo $10^9+7$, on a new line.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. 

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines consists of two space-separated positive integers describing the respective values of $n_i$ and $k_i$ for the query.

Constraints

$1\leq q\leq10$   
$1\leq n\leq10^{6}$ 
$1\leq k\leq n$  

Subtasks

$1\leq n\leq1000$  for $\textbf{40\%}$ of the maximum score.

Output Format

For each query, print the number of different beautiful sets of size $\boldsymbol{\mbox{k}}$ that can be generated using integers in the inclusive range from $1$ to $n$ on a new line. As the answers to these queries can be quite large, each answer must be modulo $10^9+7$. 

Sample Input
2
6 4
27 2

Sample Output
6
26

Explanation

For the first query, the beautiful sets of size $k=4$ we can create using numbers from $1$ to $n=6$ are shown below:

$\{1,2,3,4\}$
$\{2,3,4,5\}$
$\{3,4,5,6\}$
$\{1,2,4,5\}$
$\{1,2,5,6\}$
$\{2,3,5,6\}$

As there are are six such sets, we print the result of $6\%(10^9+7)=6$ on a new line.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
mod = 1000000007
factlist = [1]
for i in range(2000000):
	factlist.append(factlist[-1] * (i + 1) % mod)
factinvlist = [0] * len(factlist)
factinvlist[-1] = pow(factlist[-1], mod - 2, mod)
for i in range(len(factlist) - 1, 0, -1):
	factinvlist[i - 1] = factinvlist[i] * i % mod

def choose(n, r):
	if n < r:
		return 0
	else:
		return factlist[n] * factinvlist[r] * factinvlist[n - r] % mod
q = int(input())
for _ in range(q):
	[n, k] = list(map(int, input().split()))
	if k == 0:
		print(1)
	else:
		toprint = 0
		for i in range(1, k // 2 + 1):
			extra1s = k - 2 * i
			choice1s = choose(extra1s + i - 1, i - 1)
			extra0s = n - k - i + 1
			choice0s = choose(extra0s + i, i)
			toprint += choice1s * choice0s
		print(toprint % mod)


mod = 1000000007
factlist = [1]
for i in range(2000000):
	factlist.append(factlist[-1] * (i + 1) % mod)
factinvlist = [0] * len(factlist)
factinvlist[-1] = pow(factlist[-1], mod - 2, mod)
for i in range(len(factlist) - 1, 0, -1):
	factinvlist[i - 1] = factinvlist[i] * i % mod

def choose(n, r):
	if n < r:
		return 0
	else:
		return factlist[n] * factinvlist[r] * factinvlist[n - r] % mod
q = int(input())
for _ in range(q):
	[n, k] = list(map(int, input().split()))
	if k == 0:
		print(1)
	else:
		toprint = 0
		for i in range(1, k // 2 + 1):
			extra1s = k - 2 * i
			choice1s = choose(extra1s + i - 1, i - 1)
			extra0s = n - k - i + 1
			choice0s = choose(extra0s + i, i)
			toprint += choice1s * choice0s
		print(toprint % mod)


mod = 10 ** 9 + 7

def gcdExtended(a, b):
	if a == 0:
		return (0, 1)
	(x1, y1) = gcdExtended(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (x, y)

def inv(n):
	n = n % mod
	(x, y) = gcdExtended(n, mod)
	return x

def sol(n, k):
	if n == 0 or k == 0:
		return 1
	if n == 1 or k == 1 or n < k:
		return 0
	if k == 2:
		return n - 1
	if k == 3:
		return n - 2
	if k == n - 1:
		return k - 1
	if k == n:
		return 1
	kk = k // 2
	k2 = k - 2
	s = 0
	nk = n - k
	imax = min(kk, nk + 1)
	for i in range(imax):
		s += F[k2 - i] * inv(F[i] * F[i + 1] * F[k2 - 2 * i] * F[nk - i]) % mod
	s = s * F[nk + 1] % mod
	return s
q = int(input())
data = []
Nmax = 0
for i in range(q):
	(n, k) = map(int, input().split())
	N = n - k
	if N > Nmax:
		Nmax = N
	if k > Nmax:
		Nmax = k
	data.append([n, k])
F = [1]
f = 1
for i in range(1, Nmax + 2):
	f = f * i % mod
	F.append(f)
for i in range(q):
	(n, k) = data[i]
	print(sol(n, k))


q = int(input())
queries = [tuple((int(x) for x in input().split())) for _ in range(q)]
max_k = max((k for (n, k) in queries))
P = 1000000007

def pow10(r):
	r2 = r * r % P
	r5 = r2 * r2 * r % P
	return r5 * r5 % P

def minv(r):
	r5 = r * r % P
	r5 = r5 * r5 * r % P
	r10 = r5 * r5 % P
	r10 = pow10(pow10(r10))
	r10 = pow10(pow10(pow10(r10)))
	r10 = pow10(pow10(pow10(r10)))
	return r5 * r10 % P
inverses = [0] * (1 + max_k)
inverses[0] = 1
inverses[1] = 1
for i in range(2, len(inverses)):
	inverses[i] = minv(i)

def size_beautiful(n, k):
	if k < 2:
		return 0
	tag = n + 1 - k
	total = tag
	for r in range(2, min(k + 1 // 2, n - k + 1) + 1):
		tag = tag * (n - k - r + 2) % P
		tag = tag * inverses[r] % P
		tag = tag * (k - 2 * r + 2) % P
		tag = tag * (k - 2 * r + 1) % P
		tag = tag * inverses[k - r] % P
		tag = tag * inverses[r - 1] % P
		total = (total + tag) % P
	return total
for (n, k) in queries:
	print(size_beautiful(n, k))