1217  How many solutions?
Time Limit : 6 Second
Memory Limit : 128 MB
Submission: 172
Solved: 78
 Description
 How many solutions of the equation X1*X2+X2*X3+X3*X4+...+Xn1*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