NAJTREE - Tree
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 |