# The Multiplication

Criterion 2020 Round 6
Limits 2s, 512 MB

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

InputOutput
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