Koch Snowflakes

The Koch snowflake can be constructed by starting with an equilateral triangle, then recursively altering each line segment as follows:

1. divide the line segment into three segments of equal length.
2. draw an equilateral triangle that has the middle segment from step 1 as its base and points outward.
3. remove the line segment that is the base of the triangle from step 2.

Below is a figure of Koch snowflake of order 1, 2, 3 and 4.

Given the order $N$, of the Koch Snowflake, you need to find the number of peak vertices and edges of the koch snowflake.

Input

First line will contain $T$ ($T \le 10000$), the number of test cases. Each of the $T$ lines will contain one integer $N$ ($0 < N \le 10^{18}$).

Output

For each case, print the number of vertices and edges for Koch Snowflake of order $N$ modulo $1,000,000,007$.

Sample

2
1
2

Case 1: 3 3
Case 2: 6 12