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= and k=. There are  solutions. They are

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

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 (≤ ), denoting the number of test cases.

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

Output

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

Sample Input

Output for Sample Input

Case :

Case :

Case :

Case : 

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<math.h>

#include<queue>

#include<stack>

#include <map>

#include <string>

#include <vector>

#include<iostream>

using namespace std;

#define N 3000006

#define INF 0x3f3f3f3f

#define LL long long

#define mod 1000000007

LL arr[N];

void Init()

{

    arr[] = ;

    for(int i=;i<=N;i++)

    {

        arr[i] = (arr[i-]*i)%mod;

        arr[i] %= mod;

    }

}

LL quick(LL a, LL b)

{

    a = a%mod;

    LL ans = ;

    while(b)

    {

        if(b&)

            ans = ans*a%mod;

        a = a*a%mod;

        b /= ;

    }

    return ans %mod;

}

LL solve(LL a, LL b, LL c)

{

    if(b>a)

        return ;

    return arr[a] * (quick(arr[b] * arr[a-b],c-)) %mod;///利用乘法逆元

}

int main()

{

    Init();

    int T;

    int con=;

    scanf("%d",&T);

    while(T--)

    {

        LL n,k;

        scanf("%lld %lld",&n,&k);

        printf("Case %d: %lld\n",con++,solve(n+k-,k-,mod));///Cn-k+1(k-1);

    }

    return ;

}