The Multiplication

shefin 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

Submit

Login to submit.

Statistics

15% Solution Ratio
NirjhorEarliest, Apr '20
fsshakkhorFastest, 0.5s
NirjhorLightest, 131 kB
eftikhar_azimShortest, 593B
Toph uses cookies. By continuing you agree to our Cookie Policy.