Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sofdor Ali and Radioactivity

By jackal_1586 · Limits 1.5s, 512 MB

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

InputOutput
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.

Discussion

Statistics


31% Solution Ratio

nfssdqEarliest, Feb '16

Valentin_EFastest, 0.4s

tesseractLightest, 131 kB

tesseractShortest, 1656B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.