Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Koch Snowflakes

By maruf_0011 · 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 < 10000), the number of test cases. Each of the
T lines will contain one integer N (0 < N < 10^18).

Output

For each case, print the number of vertices and edges for koch snowflake of
order N modulo 1000,000,007.

Sample

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

Statistics

68% Solution Ratio

One_ElephantEarliest, Dec '16

experimenterFastest, 0.0s

oneoff.QtSOcNcx54Lightest, 393 kB

cryptoshawonShortest, 464B

Submit

 AB Bank IUT 8th ICT Fest Programming Contest Nov '16 IUT 8th ICT Fest Programming Contest (Replay) Dec '16 