John’s Tree

Little John is very interested about constructing a rooted tree with the following constraints:

1. 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.
2. 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