Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Multiplication

By shefin · 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

Discussion

Statistics


15% Solution Ratio

NirjhorEarliest, Apr '20

fsshakkhorFastest, 0.5s

NirjhorLightest, 131 kB

eftikhar_azimShortest, 593B

Submit

Login to submit

Editorial

The main idea is: for each k, pre-calculate all possible values of ((1+k) × (1+2k) × ... × (1+ik)) m...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.