# Koch Snowflakes

IUT 8th ICT Fest Programm...
Limits 1s, 512 MB

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

InputOutput
2
1
2

Case 1: 3 3
Case 2: 6 12


### Submit

iutictf8.37$0M8YoEarliest, Nov '16 experimenterFastest, 0.0s iutictf8.37$0M8YoLightest, 393 kB