This ICPC will take place in a huge hall room which can be divided into N x N square cells. That's why the organizers will assign 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: Guard Placement	Fig 2: Guard Groups

Suppose we have a hall room that can be divided into 6 x 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 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 ≤ 10⁵, 1 ≤ K ≤ min(N, 50)).

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 1000000007 (10⁹ + 7).