The Multiplication

Nafis is working on a mathematical project. But he is stuck on a step of it. In this step, numerous multiplications need to be performed. He needs a lot of time to do this. But as there's a shortage of time, there's no scope of spending a lot of time on this one task. So, he is asking you to do the task in a short amount of time.

Nafis will give you the value of two integers n and k. All you have to do is calculating the result of the expression: ((1 + k) × (1 + 2k) × (1 + 3k) × ⋯ × (1 + ck)) % m where c is the largest integer such that ck ≤ n and m = 109+7.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 103), the number of the test cases.

In each of the cases, there will be a line containing two integers k (2 ≤ k ≤ 40) and n (8 ≤ n ≤ 227). It is guaranteed that n ≥ 4k.

Output

For each case, print “Case x: y” (without the quotes) in a single line, where x is the case number y is the result of the case. Output the number modulo m that means y % m.

Sample

Input	Output
5 2 8 2 9 5 23 4 19 3 12	Case 1: 945 Case 2: 945 Case 3: 22176 Case 4: 9945 Case 5: 3640