Description

To carry out this algorithm, Mirko chose $4$ points that form a perfect square. Then he started doing the following steps:

• On each side of every square, Mirko adds a new point exactly in the middle. The terrain height at this new point is the average of the heights at the two endpoints of that side.
• At the exact center of every square, Mirko also adds a new point. The terrain height at this new point is the average of the heights of all $4$ vertices of the square plus a small random value.

After finishing all the operations above once, Mirko gets $4$ new squares. He keeps creating new squares like this until he is satisfied with the result. The figure below shows the initial state of the algorithm, $1$ iteration, and $2$ iterations.

Mirko noticed that some points belong to more than one square. To reduce memory usage, he stores such points only once, but once a point is stored, it will stay in memory forever. Now he wants you to write a program to tell him, after $n$ iterations, how many points in total need to be stored in memory.

Input Format

The input contains only one integer $n$, which represents the number of iterations.

Output Format

Output only one integer, which is the number of points that need to be stored in memory after $n$ iterations.

1

9

2

25

5

1089

Hint

Constraints

For all testdata, $1\leqslant n\leqslant 15$.

Source

This problem comes from COCI 2009-2010 CONTEST 4 T2 PLANINA, and with the original testdata settings, the full score is $50$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5