Bear-Baby

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Bear-Baby is a smart boy and he likes playing games. One day he played a simple game with one guy. In this game there are N piles of stones, and each of these piles has K stones at first. When the game starts, two participants take turns to pick up stones following this rule: the one who should act now must choose two different piles (e.g. , pile i and j, i≠j ), and remove the same number of stones from these two piles. The one who cannot act loses the game. Now Bear-Baby wants to study the game. He’d like to figure out the Sprague-Grundy value of each situation that will appear during the game.
Given the number of the piles N and the size of each pile K, Bear-Baby wonders how many different situations could appear during the game. We consider that two situations are the same if they are same after reorder the piles, i.e situations (1,1,3) (1,3,1) and (3,1,1) are the same.

Input

There is an integer T(T<=100) in the first line indicating the number of test cases.
  In each test case there are two numbers N and K (1<=N,K<=100) telling the number of piles and the size of each pile in one line.

Output

For each test case: output the case number as shown and print the number of different situations in one line. The answer may be a very large number, so print the answer modulo 1000000007.

Sample Input

2 2 3 3 2

Sample Output

Case #1: 4 Case #2: 5
Hint
For the Case #2, from the initial situation (2,2,2), we can get five different situations (2,2,2) (1,1,2) (0,0,2) (0,1,1) (0,0,0)

Hint

xubiao

Source

2011 Multi-University Training Contest 11 -

提交代码