### COCI 2009/2010, Contest #4

## Task PLANINA

Mirko and Slavko are filming a movie adaptation of the popular SF novel "Chicks in space 13". The script requires them to present a lot of different worlds so they decided to film the entire 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 **midpoint displacement algorithm**.

To start the algorithm, Mirko selects 4 points forming a perfect square. He then performs the following steps:

- On each side of the square, he adds a new point in the exact middle of the side. The height of this new point is the average height of the two points on that side.
- In the exact center of the square he adds a new point whose height is the average height of all 4 square vertices, plus a small random value.

After those two steps are performed, he now has 4 new squares. He performs the same steps on the newly created squares again and again until he is pleased with the results. The following diagram illustrates 2 iterations of the algorithm.

Mirko noticed that some of the points belong to more than one square. In order to decrease memory consumption, he stores calculates and stores such points **only once**. He now wonders how many points in total will he need to store in memory after **N** iterations.

### Input

The first and only line of input contains one integer **N** (1 ≤ **N** ≤ 15), the number of iterations.

### Output

The first and only line of output should contain one number, the number of points stored after **N** iterations.

### Sample Tests

## Input1 ## Output9 |
## Input2 ## Output25 |
## Input5 ## Output1089 |

All Submissions

Best Solutions

**Point Value:** 5

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Jul 14, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

magicalsoupon Feb 17, 2018 - 4:11:31 pm UTC its just a simple algorithm