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

Discussion

Statistics


68% Solution Ratio

One_ElephantEarliest, Dec '16

experimenterFastest, 0.0s

oneoff.QtSOcNcx54Lightest, 393 kB

cryptoshawonShortest, 464B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.