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.

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.

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.

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.

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.

提交代码