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.
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.
