In a cloudy autumn afternoon, Mr. Fallen felt to write some poems. As you might already have known he is very poor at poetry. So after quite some trying he changed his mind and tried to learn a new game- Chomp.
The game chomp is a two player game, played in a 2D rectangular board. The board has M rows and each of the rows has N columns initially, so N * M cells in total. You can consider that the leftmost bottom cell of the board is at co-ordinate (1, 1) and the rightmost top cell is at co-ordinate (N, M). In a turn, a player should select a cell of the board and all the cells with both X and Y co-ordinates greater than or equal to the selected cell gets removed from the board. The turn of the player alters and the one with the last move loses.
After trying the game for a while Mr. Fallen did understand that this game is too hard for him! Instead he thought if he could play with arbitrary valid moves, how many different boards could he see throughout the game including the empty one.
He tried and tried and kept failing and finally he came up with the smart idea to use brilliant mind like you to help him solving this problem. Help him to find total number of different boards possible to make from the given board with valid moves. Two boards will be considered different if a cell exists in one but not in the other.
The first line of the input contains an integer T (T <= 100,000) denoting the number of test cases. Each of the following T lines has two space separated integers M and N (1 <= M, N <= 100,000).
For each input, print the output in the format, “Case C: X” (quote for clarity), where X is the number of different boards possible including the empty board modulo 1,000,000,007.
For exact output format please check sample input/output section.
|Case 1: 2
Case 2: 3