Z15 lives in a strange planet. He wants to be best competitive programmer of his planet. Now he is learning data structures. Today his teacher, named Mr. Y, is teaching M-tree. In his planet, M-tree is a defined as a tree, in which every parent has m child. After completion of teaching, Z15 has been given a task. Given m and number of level (l) the tree contains, what is the total number of node in that tree?

Input

Input set starts with an integer (T <= 100,000), denoting the test case. Then T test case follows.

Each case starts with two integer (1 <= m <= 100,000 and 1 <= l <= 100,000)

Output

For each case print case number and total number of nodes the tree can have. As the answer can be very large, print the answer modulo 1,000,000,007.

Example

Input:
3
2 4
4 4
2 3

Output:
Case 1: 31
Case 2: 341
Case 3: 15