John’s Tree
Little John is very interested about constructing a rooted tree with the following constraints:
- A tree of depth D means that the tree should contain at least 1 node which is exactly D distance away from the root and there is no node of more than D distance from the root.
- The degree of a node of the tree cannot be greater than V . Degree of a node is simply measured by the number of nodes it is directly connected to, via a single edge.
John wonders about the maximum number of nodes in a tree following the rules described above. For example, if D = 1 and V = 2, then the maximum number of nodes in the tree is 3.
Input
First line of the input contains a positive integer T (T ≤ 150). Each of the following T lines contains twointegersD(0≤D≤2∗109)andV (1≤V ≤2∗109),respectively.
Output
Foreachcase,printalineoftheform‘Case : ’,wherexisthecasenumberandyisthe maximum possible number of nodes in the tree. As the value of y can be quite large, print the value modulo 1000000007 (109 + 7). If it is not possible to construct the tree, print ‘Case < x >: -1’.
Sample Input
3 01 12 15
Sample Output
Case 1: 1
Case 2: 3
Case 3: 6