Oh Functions

MU Team Practice Contest...
Limits 1s, 512 MB

Let’s define functions f and g as:

f(x) = 2 * ( f(x-1) + g(x-1) - 1 ) * ( f(x-1) + g(x-1) - 3 ) + 12 * f(x-1) - 13

g(x) = ( f(x-1) + g(x-1) ) * ( f(x-1) + g(x-1) - 4 ) + 12 * g(x-1) + 7

And f(0) = 2, g(0) = 1.

Here, x is non-negative integers. For giving a value of x, find the value of f(x) and g(x).

Input

First line of the input is T (T ≤ 50000), then T test cases follows. Each case has only one line containing a positive integer x (1 ≤ x ≤ 1014).

Output

For each test case print a line in Case I: F G format where I is case number and F is f(x) and G is g(x). As F and G can be very big number, output them with modulo 1,000,000,007.

Sample

InputOutput
4
1
2
3
4
Case 1: 11 16
Case 2: 1367 820
Case 3: 9564839 4784068
Case 4: 261293629 130666607

Submit

Login to submit.

Statistics

58% Solution Ratio
NirjhorEarliest, Nov '16
saquib2508Fastest, 0.2s
mahbubcsejuLightest, 1.6 MB
saquib2508Shortest, 899B
Toph uses cookies. By continuing you agree to our Cookie Policy.