kalas-army

King Kala the Fighter has an army of N soldiers. Each soldier is either a BanVeer or a TalwarBaaz. There are M soldiers in the army who are TalwarBaaz. The King forms a strategy. For each battle, he doesn’t have the resources to send his army in groups of more than K soldiers. Now, a group of at most K soldiers can win the battle if and only if there is at least one TalwarBaaz in the group. Count the number of ways that a group can be formed that wins the battle.

Input

The first line will contain the number of battles T. For each battle, three space separated integers N, M and K are given.

Output

For each battle, print the required answer modulo 10^9+9.

Constraints

1 ≤ T ≤ 100
1 ≤ N, K ≤ 2 x 10^5
1 ≤ M ≤ N

*Subtask 1 (40 points): *
N = K

*Subtask 2 (40 points): *
N, K ≤ 500

*Subtask 3 (200 points): *
Original Constraints

Note: For each subtask, the rest of the constraints remain the same except the ones mentioned.

SAMPLE INPUT
3
2 2 2
4 2 3
10 4 3

SAMPLE OUTPUT
3
11
134

Explanation

In the first case, the groups with at least one TalwarBaaz can be formed in total three ways, i.e. the King can send the first or the second Talwarbaaz alone, or send them both together.

In second case, he can form 2 groups of size 1, 5 groups of size 2, and 4 groups of size 3, making a total of 11 ways.

Source: hackerearth | Difficulty: EASY


Solutions:
fact = [0]*200005
inv = [0]*200005
MOD = 1000000009

def invMod (n):
	return pow(n, MOD-2, MOD)

def solve (n, r):
	if r < 0 or r > n:
		return 0
	x = ( fact[n] * ( inv[r]%MOD * inv[n-r]%MOD)%MOD)%MOD
	return x

def main():
	fact[0] = 1
	inv[0] = 1
	for i in range(1,200003):
		fact[i] = (fact[i-1]*i)%MOD
		inv[i]  = invMod(fact[i])
	tc = int(input())
	while  tc>0:
		tc = tc - 1
		n, m, k = list(map(int, input().split()))
		ans = 0
		for i in range(1,k+1):
			ans = (ans + solve(n,i) - solve(n-m,i) + MOD)%MOD
		print(ans)

main()


fact = [0]*200005
inv = [0]*200005
MOD = 1000000009

def invMod (n):
	return pow(n, MOD-2, MOD)

def solve (n, r):
	if r < 0 or r > n:
		return 0
	x = ( fact[n] * ( inv[r]%MOD * inv[n-r]%MOD)%MOD)%MOD
	return x

def main():
	fact[0] = 1
	inv[0] = 1
	for i in range(1,200003):
		fact[i] = (fact[i-1]*i)%MOD
		inv[i]  = invMod(fact[i])
	tc = int(input())
	while  tc>0:
		tc = tc - 1
		n, m, k = list(map(int, input().split()))
		ans = 0
		for i in range(1,k+1):
			ans = (ans + solve(n,i) - solve(n-m,i) + MOD)%MOD
		print(ans)

main()