Tug of war is a sport that directly puts two teams against each other in a test of strength.

During school days, both Chef Shifu and Chef Po were champions of tug of war.
On behalf of restaurant's anniversary, Chef Shifu and Chef Po have decided to conduct 
a tug of war game for their customers.

Master Chef Oogway has decided the following rules for the game.

Let N be the number of players participating in the game. All of these 
players would stand in a circle in clock wise direction.
    
There are an infinite number of long ropes available.
When a rope is held by exactly two players, it is termed as bonding.
    
At least one bonding is necessary to conduct a game.
    
A player can play against multiple people simultaneously i.e he can have more than one bonding at
the same time. 
    
Both members of a pair of players that have a bonding must have the same number of total
bondings. That is, if the player A  makes bonding with the player B,
then the number of total bondings of the player A must be the same as
that of the player B.
    
Bondings should be created in such a fashion that ropes must not intersect each other. 
    
The number of bondings of every player must be no more than K.
    
Now Master Chef Oogway asked Chef Shifu and Chef Po to find out the number of possible games.
Your task is to help them find this number. As this number might become huge,
you've to find it modulo (10^{14}+7). Two games are different iff there is some
bonding that is present in only of them. 

------ Input ------ 

First line contains T, the number of test cases.
Each of T lines contain 2 positive integers N and K separated by a space.

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

For each test case, output the number of ways to conduct the game modulo 100000000000007 (10^{14}+7) in one line.

------ Example ------ 

Input:
3
3 2
4 0
2 1

Output:
4
0
1

Explanation:

For the 1st case, there are 3 players. Let's call them p1, p2, p3.
Different games possible are:

Game 1: p1-p2 (numbers of bondings of p1, p2 are 1 ≤ K = 2)

Game 2: p1-p3 (numbers of bondings of p1, p3 are 1 ≤ K = 2)

Game 3: p2-p3 (numbers of bondings of p2, p3 are 1 ≤ K = 2)

Game 4: p1-p2, p1-p3, p2-p3 (numbers of bondings of p1, p2, p3 are 2 ≤ K
= 2)

For the 2nd test case, we cannot form the game, because K = 0 and hence no
player is allowed to make any bonding. As any game must have atleast one
bonding, no game is possible here. 

For the 3rd case, only possible game is:

Game 1: p1-p2 (number of bondings in p1, p2 are 1)

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

1 ≤ T ≤ 10000
0 ≤ N ≤ 10000
0 ≤ K ≤ N

Difficulty: VERY_HARD
Tags: Combinatorics

Complete search

Mathematics

Matrices

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
import sys
mod = 100000000000007
motzkin = [1, 0]
catalan = [1, 1, 2]
for i in range(1, 10009):
	motzkin.append(0)
for j in range(0, 10006):
	catalan.append(0)
for i in range(2, 10006):
	motzkin[i] = (i - 1) * (2 * motzkin[i - 1] + 3 * motzkin[i - 2])
	motzkin[i] = motzkin[i] // (i + 1)
for i in range(10003):
	motzkin[i] = (motzkin[i] + motzkin[i + 1]) % mod
for i in range(2, 10001):
	catalan[i + 1] = (4 * i + 2) * catalan[i] // (i + 2)
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if k == 0:
		print(0)
	elif k == 1:
		print((motzkin[n] - 1) % mod)
	else:
		print((catalan[n] - 1) % mod)


import sys
modu = 100000000000007
motzkina = [1, 0]
catalana = [1, 1, 2]
for i in range(1, 10009):
	motzkina.append(0)
for j in range(0, 10006):
	catalana.append(0)
for i in range(2, 10006):
	motzkina[i] = (i - 1) * (2 * motzkina[i - 1] + 3 * motzkina[i - 2])
	motzkina[i] = motzkina[i] // (i + 1)
for i in range(10003):
	motzkina[i] = (motzkina[i] + motzkina[i + 1]) % modu
for i in range(2, 10001):
	catalana[i + 1] = (4 * i + 2) * catalana[i] // (i + 2)
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if k == 0:
		print(0)
	elif k == 1:
		print((motzkina[n] - 1) % modu)
	else:
		print((catalana[n] - 1) % modu)


import math
osn = 100000000000007
res2 = [1, 1]
const = 10001
for i in range(2, const):
	res2.append((res2[i - 2] * (3 * i - 3) + res2[i - 1] * (2 * i + 1)) // (i + 2))
res3 = [1, 1]
for i in range(2, const):
	res3.append(res3[i - 1] * (2 * i) * (2 * i - 1) // (i * (i + 1)))
t = int(input())
for i in range(t):
	kp = input().split(' ')
	query = []
	for k in range(len(kp)):
		query.append(int(kp[k]))
	if query[-1] == 0:
		print(0)
		continue
	if query[-1] == 1:
		print((res2[query[0]] - 1) % osn)
		continue
	print((res3[query[0]] - 1) % osn)


mod = 100000000000007
inv = 97538920113599
fact = [1]
inv_mod = []
motzkin = [1, 0]
catalan = [1, 1, 2]
for i in range(1, 10009):
	fact.append(fact[i - 1] * i % mod)
	motzkin.append(0)
for j in range(0, 10006):
	inv_mod.append(pow(fact[j], inv, mod))
	catalan.append(0)
for i in range(2, 10006):
	motzkin[i] = (i - 1) * (2 * motzkin[i - 1] + 3 * motzkin[i - 2])
	motzkin[i] = motzkin[i] // (i + 1)
for i in range(10003):
	motzkin[i] = (motzkin[i] + motzkin[i + 1]) % mod
for i in range(2, 10001):
	catalan[i + 1] = (4 * i + 2) * catalan[i] // (i + 2)
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if k == 0:
		print(0)
	elif k == 1:
		print((motzkin[n] - 1) % mod)
	else:
		print((catalan[n] - 1) % mod)


import sys
dp1 = [1, 1]
dp2 = [1, 1]
N = 10010
M = 100000000000007
for i in range(2, N):
	dp1.append((3 * (i - 1) * dp1[i - 2] + (2 * i + 1) * dp1[i - 1]) // (i + 2))
	dp2.append(2 * (2 * i - 1) * dp2[i - 1] // (i + 1))
t = int(input())
while t:
	t = t - 1
	(n, k) = input().split()
	if int(k) == 0:
		print('0')
	elif int(k) == 1:
		print((dp1[int(n)] - 1 + M) % M)
	else:
		print((dp2[int(n)] - 1 + M) % M)


import sys, re, copy
inf = sys.stdin
MOD = int(100000000000000.0 + 7)

def mpow(a, b):
	res = 1
	while b > 0:
		if b & 1 > 0:
			res = res * a % MOD
		a = a * a % MOD
	return res

def minv(x):
	y = mpow(x, MOD - 2)
	assert x * y % MOD == 1
	return y
maxn = int(10000.0 + 10)
dyn = [0] * (maxn + 1)
dyn[0] = 1
dyn[1] = 1
for i in range(1, maxn):
	dyn[i + 1] = (dyn[i] * (2 * i + 3) + dyn[i - 1] * (3 * i)) // (i + 3)
f = filter(lambda x: x != '', re.compile('[\n ]').split(inf.read()))
f = list(reversed(list(map(int, f))))
kat = [0] * (maxn + 1)
kat[0] = 1
for i in range(0, maxn):
	kat[i + 1] = 2 * (2 * i + 1) * kat[i] // (i + 2)
tn = f.pop()
for _ in range(tn):
	n = f.pop()
	k = min(2, f.pop())
	if k == 0:
		ans = 0
	elif k == 2:
		ans = kat[n] - 1
	else:
		ans = dyn[n] - 1
	print(ans % MOD)