## 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 3Output: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 |