Consider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.

Input: 

The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.

Output: 

Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.

Constraints: 

1 <= T <= 10000 

4 <= N <= 10^9 

1 <= K <= N 

Sample Input: 

3 

4 1 

5 2 

5 3

Sample Output: 

2 

5 

0

Explanation:

For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order). 

For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.

Difficulty: MEDIUM_HARD
Tags: Geometry

Starter code:

Solutions:
MOD = 1000003

def inv(x):
	return pow(x, MOD - 2, MOD)
Fact = [1] * MOD
for i in range(2, MOD):
	Fact[i] = i * Fact[i - 1] % MOD

def fact_val(n):
	q = MOD
	v = 0
	while q <= n:
		v += n // q
		q *= MOD
	return v

def fact(n):
	(q, r) = divmod(n, MOD)
	return pow(Fact[MOD - 1], q, MOD) * Fact[q] * Fact[r] % MOD

def binom(n, p):
	assert 0 <= p <= n
	val = fact_val(n) - fact_val(p) - fact_val(n - p)
	f = fact(n) * inv(fact(p)) * inv(fact(n - p)) % MOD
	return (f, val)

def form(n, k):
	n -= 3
	if k > n:
		return 0
	(f1, v1) = binom(n + k + 2, k)
	(f2, v2) = binom(n, k)
	v3 = 0
	K = k + 1
	while K % MOD == 0:
		v3 += 1
		K //= MOD
	if v1 + v2 - v3 > 0:
		return 0
	assert v1 + v2 == v3
	return f1 * f2 * inv(K) % MOD
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	print(form(N, K))


mod = 1000003
factlist = [1]
factinvlist = [mod - 1] * mod
for i in range(1, mod):
	factlist.append(factlist[-1] * i % mod)
	factinvlist[mod - i - 1] = factlist[i] if i % 2 == 1 else mod - factlist[i]

def choose(n, r):
	toret = 1
	currn = n
	currr = r
	while currn > 0:
		if currr % mod > currn % mod:
			return 0
		else:
			toret = toret * factlist[currn % mod] * factinvlist[currr % mod] * factinvlist[(currn - currr) % mod] % mod
		currn //= mod
		currr //= mod
	return toret
t = int(input())
for _ in range(t):
	[n, k] = list(map(int, input().split()))
	if k > n - 3:
		print(0)
		continue
	if (k + 1) % mod == 0:
		if (n - 3 - k) % mod == 0:
			toret = choose(n - 3, k) * choose(n + k - 1, k + 1) * pow(n - 1, mod - 2, mod) % mod
		else:
			toret = choose(n - 3, k + 1) * choose(n + k - 1, k) * pow(n - 3 - k, mod - 2, mod) % mod
	else:
		toret = choose(n - 3, k) * choose(n + k - 1, k) * pow(k + 1, mod - 2, mod) % mod
	print(toret)


MOD = 1000003

def inv(x):
	return pow(x, MOD - 2, MOD)
Fact = [1] * MOD
for i in range(2, MOD):
	Fact[i] = i * Fact[i - 1] % MOD

def fact_val(n):
	q = MOD
	v = 0
	while q <= n:
		v += n // q
		q *= MOD
	return v

def fact(n):
	(q, r) = divmod(n, MOD)
	return pow(Fact[MOD - 1], q, MOD) * Fact[q] * Fact[r] % MOD

def binom(n, p):
	assert 0 <= p <= n
	val = fact_val(n) - fact_val(p) - fact_val(n - p)
	f = fact(n) * inv(fact(p)) * inv(fact(n - p)) % MOD
	return (f, val)

def form(n, k):
	n -= 3
	if k > n:
		return 0
	(f1, v1) = binom(n + k + 2, k)
	(f2, v2) = binom(n, k)
	v3 = 0
	K = k + 1
	while K % MOD == 0:
		v3 += 1
		K //= MOD
	if v1 + v2 - v3 > 0:
		return 0
	assert v1 + v2 == v3
	return f1 * f2 * inv(K) % MOD
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	print(form(N, K))