Server Time: Tue Nov 12, 2019 4:10 am
Welcome ( logout
1102 - Problem Makes Problem
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

As I am fond of making easier problems, I discovered a problem. Actually, the problem is 'how can you make n by adding k non-negative integers?' I think a small example will make things clear. Suppose n=4 and k=3. There are 15 solutions. They are

1.      0 0 4

2.      0 1 3

3.      0 2 2

4.      0 3 1

5.      0 4 0

6.      1 0 3

7.      1 1 2

8.      1 2 1

9.      1 3 0

10.  2 0 2

11.  2 1 1

12.  2 2 0

13.  3 0 1

14.  3 1 0

15.  4 0 0

As I have already told you that I use to make problems easier, so, you don't have to find the actual result. You should report the result modulo 1000,000,007.

Input

Input starts with an integer T (≤ 25000), denoting the number of test cases.

Each case contains two integer n (0 ≤ n ≤ 106) and k (1 ≤ k ≤ 106).

Output

For each case, print the case number and the result modulo 1000000007.

Sample Input

Output for Sample Input

4

4 3

3 5

1000 3

1000 5

Case 1: 15

Case 2: 35

Case 3: 501501

Case 4: 84793457

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan