P7695 [COCI 2009/2010 #4] PLANINA

Mirko and Slavko are filming a movie adapted from the sci-fi novel _Chicks in space 13_. The script requires them to show different worlds, so they decided to film the whole movie in front of a green screen and add CGI backgrounds later. Mirko heard that the best way to generate artificial terrain is to use the **midpoint displacement algorithm**.

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.

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

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

**Constraints** For all testdata, $1\leqslant n\leqslant 15$. **Source** This problem comes from **_[COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST 4](https://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf) T2 PLANINA_**, and with the original testdata settings, the full score is $50$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5