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