EIDSALAMI2 - Again Eid Salami

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


Added by:Raihat Zaman Neloy
Date:2016-07-22
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2020-04-21 00:07:55
Whichever indonesian genius decided to assign this problem to his students, clearly doesn't understand than half of them are copypasting the same solution to get it over with while lowering the score for everyone else.

Use https://www.spoj.com/contests/ to set up own contest where you can also view sources and weed out the lamers.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.