This ICPC will take place in a huge hall room which can be divided in to N × N square cells. That’s why some volunteers will guard this room. But each row (or column) should be guarded by exactly two volunteers. And in a single cell at most one volunteer can be placed. Now volunteers can watch other volunteers either vertically or horizontally. Thus the volunteers form different groups. To be more specific, in a single group all the volunteers can look after each other directly or indirectly. Fig 1 Fig 2 Suppose we have a hall room that can be divided into 6×6 square cells. Circles represent volunteers; lines represent the connectivity of the groups. In Fig 1, there is only one group (check the solid lines carefully). In Fig 2, there are two groups, one group is shown using solid lines, and another one is shown using dotted lines. Now the organizers wanted to know the number of ways they can place volunteers in the hall room such that they form exactly K groups. Two configurations will be different if in one configuration there is a volunteer on a cell but the cell is empty in another one. So, the organizers are seeking your help as you are one of the best programmers in town. Input Input starts with an integer T (≤ 50000), denoting the number of test cases. Each case starts with a line containing two integers: N and K (2 ≤ N ≤ 105, 1 ≤ K ≤ min(N, 50)). Output For each case, print the case number and the number of ways the volunteers can be placed in the hall room as guards. The result can be large, so print the result modulo 1000 000 007. Sample Input 4 21 31 41 42
2/2 Sample Output Case 1: 1 Case 2: 6 Case 3: 72 Case 4: 18