ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## J. Zones on a Plane

Time limit: 1.0 second
Memory limit: 64 MB Consider zones zi on a plane which consist of triangles. Zone z1 consists of two right-angled isosceles triangles, forming a square. Zone zn + 1 is produced from zone zn in the following way. For each triangle from the previous zone, construct two isosceles right-angled triangles on each of its two legs as a hypotenuse. Then, remove every triangle that is a part of a zone with lower number. The remaining triangles constitute the zone zn + 1.
Given an integer number n, find how many simple polygons constitute the zone zn.

### Input

There is a single integer n (1 ≤ n ≤ 2000) on the first line of the input.

### Output

Output a single number — the number of simple polygons zone zn consists of.

### Samples

inputoutput
`1`
`1`
`2`
`4`
`3`
`8`
`4`
`12`
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
To submit the solution for this problem go to the Problem set: 1531. Zones on a Plane