Alice is obsessed with chocolate cookies but her mother does not like her habit of eating chocolate cookies. So. Alice's mother restricted her to eat at most N cookies per day and the cookie she ate on the (i + 1)th day should be not more than cookies she ate on the day. Alice wants to eat at least k cookies per day. After listening to her mothers restriction, your task is to determine the number of ways in which Alice can eat the cookies. As the number of ways can be very large, print the output modulo 10 + 7.
Input format
• The first line contains T denoting the number of test cases.
• Each line of a test case contains 3 space-separated integers number N, K, and M. (where M is the number of days)
Output
Print the number of possible ways to eat cookies modulo 10^9 + 7.
Constraints
1 < T < 10^6
1 < N < 10^6
1 < k < N
M < 10^6
Sample input:
2
5 2 2
7 3 3
Output:
10
35
Let us solve a simpler problem first : Assume k=1, now we have to find number of non-decreasing arrays of size M such that ar[M]<=n.
Assume the array has a1 1's followed by a2 2's, .... an n's such that a1,a2,...an >= 0. Now we know the size of the array is M. So a1+a2+a3+....+an = M. This can be solved using stars and bars theorem and the answer is (n+M-1)CM.
Now for k!=1 we can solve the problem for M and k-1 separately and subtract answer(k-1) from answer(M).
But each TESTCASE will then have time complexity of O(k*M), and since there can be 10^6 testcases, this will fail.
On the basis of constraints, we need atmost O(T*logM) solution
nCr can be computed in O(1) after O(n) or O(nlgn) pre-computation.
See link for details.