## NAJTREE - Tree

no tags

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```

 Added by: Najmuzzaman Date: 2015-04-08 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 JS-MONKEY