ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1531. Zones on a Plane

Time limit: 1.0 second
Memory limit: 64 MB
Problem illustration
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