Koch Snowflakes

maruf_0011 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 NN, of the Koch Snowflake, you need to find the number of peak vertices and edges of the koch snowflake.

Input

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

Output

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

Sample

InputOutput
2
1
2
Case 1: 3 3
Case 2: 6 12

Submit

Login to submit.

Statistics

68% Solution Ratio
iutictf8.37$0M8YoEarliest, Nov '16
experimenterFastest, 0.0s
iutictf8.37$0M8YoLightest, 393 kB
cryptoshawonShortest, 464B
Toph uses cookies. By continuing you agree to our Cookie Policy.