Server Time: Wed Feb 26, 2020 1:18 pm
Welcome ( logout
E - Guards
PDF (English) Ranklist
Time Limit: 3 second(s) Memory Limit: 64 MB

This ICPC will take place in a huge hall room which can be divided in to N x 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.

e1.png

e2.png

Fig 1

Fig 2

 

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

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                                Output for Sample Input

4

2 1

3 1

4 1

4 2

Case 1: 1

Case 2: 6

Case 3: 72

Case 4: 18



Problem Setter: Jane Alam Jan
Special Thanks: Md. Arifuzzaman Arif
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan