Problem Background

Mirko and Slavko are filming a movie adapted from the science fiction novel Chicks in space 13. The script requires them to depict different worlds, so they decide to shoot the entire film in front of a green screen and add CGI backgrounds later. Mirko learns that the best way to generate artificial terrain is by using the Midpoint Displacement Algorithm.

Problem Description

To execute this algorithm, Mirko selects four points that form a perfect square. He then proceeds with the following steps:

• On each side of the square, Mirko adds a new point at the midpoint. The terrain height at this new point is the average of the heights of the two points on that side.
• In the center of each square, Mirko also adds a new point. The terrain height at this new point is the average of the heights of all four square vertices plus a small random value.

After completing these operations once, Mirko has four new squares. He continues to create new squares until he is satisfied with the result. The figure below illustrates the initial state, one iteration, and two iterations.

Mirko realizes that some points belong to more than one square. To reduce memory consumption, he stores each point only once, but once a point is stored, it remains in memory forever. He now wants you to write a program that tells him how many points need to be stored in memory after \( n \) iterations.

Input Format

The input consists of a single integer \( n \), representing the number of iterations.

Output Format

The output consists of a single integer, representing the number of points that need to be stored in memory after \( n \) iterations.

Sample Input and Output

Sample Input #1

1

Sample Output #1

9

Sample Input #2

2

Sample Output #2

25

Sample Input #3

5

Sample Output #3

1089

Notes

[Data Range]

For all data, \( 1 \leqslant n \leqslant 15 \).

[Problem Source]

This problem is from COCI 2009-2010 CONTEST 4 T2 PLANINA, configured according to the original problem data, with a full score of 50 points.

Provided by Eason_AC for translation and整理.

见题面 Input 部分

见题面 Output 部分