1217 - How many solutions?

Time Limit: 6s Memory Limit: 128MB

Submissions: 172 Solved: 78
Description
How many solutions of the equation X1*X2+X2*X3+X3*X4+...+Xn-1*Xn=k Xi=0 or 1? For example: when n = 3 and k = 0, the answer is 5. The solutions are {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0} and {1, 0, 1}.
Input
The input contains several test cases. The first line contains the number of the test cases. Eash of the following lines contains two numbers n and k, 2<=n<=1,000,000,000 0<=k<=40.
Output
For each test case, output one line contains the answer module 9973.
Sample Input
3
3 0
3 2
2 2
Sample Output
5
1
0
Hint
Source