Mahbub has N-1 cousins. Mahbub is the oldest among them. Now they come to their uncle for "EID SALAMI". But they decided that the older one will strictly get more money than the younger. But their uncle has another plan. He told them that he will give them an amount of money and they have to tell them how many ways they can collect money so that the elder gets more money than the younger and they have to take all the money.

As they have to meet with their other relatives, so they come to you, as they know that you are a great programmer, and if you can solve their problem they will give you some SALAMI :)

Input

Input starts with an integer T, denoting the number of test cases.

Each case starts with a line containing two integers M and N. M denotes the amount of money their uncle wants to give them. N denotes the number of cousins of Mahbub (including himself).

Output

For each case, print the case number and the total number of ways. As the result can be very big, you need to output the answer module 10^9 + 7 (1000000007). See the samples for exact formatting.

Constraints

1<=T<=100

1<=M<=1000000

2<=N<=1000000

M*N <= 1000000

Example

Input:
2
40 3
12 3

Output:
Case 1: 114
Case 2: 7

Problem Setter: Raihat Zaman Neloy. Used in Eid 2016 contest. For more about Eid 2016 contest: Click Here