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).
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).
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.
| Input | Output |
|---|---|
4 1 2 3 4 | Case 1: 11 16 Case 2: 1367 820 Case 3: 9564839 4784068 Case 4: 261293629 130666607 |