Sofdor Ali and Radioactivity

Sofdor Ali is the craziest and clumsiest scientist in Bangladesh. He tries to maintain the safety measures perfectly. Yet due to his clumsiness, last month he blew his laboratory. Fortunately no one was injured or worse. Now after one month, he invented a new radioactive and explosive material. They are kept in a glass container. But there are some constraints. Blocks of container must be separated by lead separation. If more than M containers are placed side by side in a block, there cumulative radiation power will cause an explosion. Instead of keeping those materials in order, he thought of another problem, "How many ways can I do it?" Two arrangements are considered different if and only if they have different number of container blocks or they have same number of container blocks but there exists an index i for which size of i'th block differs in both arrangements. ( See the explanation of the third sample )

There are N containers of radioactive explosive. And you are given M. Can you tell the number of ways to arrange those?

Input

First line contains number of test cases T (0 < T ≤ 100). Next T line each contains two integers N and M (0 < N ≤ 1016 and 0 < M ≤ 50)

For 20% of the dataset, we have N<=7.

For 40% of the dataset, we have N<=100.

For 60% of the dataset, we have N<=1000.

For 80% of the dataset, we have N<=106.

Output

For each case print the case number and the number of ways to arrange. Follow the Output section for specific formatting. As the result can become too large, print it modulo 109+7.

Sample

3
3 3
9 2
4 2

Case 1: 4
Case 2: 55
Case 3: 5

Explanation

For the third sample where N = 4 and M = 2, let's consider the initial scenario like this:

rrrr (each r represents a container)

We can make the following arrangements:

r|r|r|r (each | represents a partitioning wall dividing a block into smaller left and right block)

r|r|rr

r|rr|r

rr|r|r

rr|rr

These are the required five partitions.