Consider zones *z*_{i} on a plane which consist of triangles. Zone *z*_{1}
consists of two right-angled isosceles triangles, forming a square. Zone
*z*_{n + 1} is produced from zone *z*_{n} 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 *z*_{n + 1}.

Given an integer number *n*, find how many simple polygons constitute
the zone *z*_{n}.

### 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 *z*_{n}
consists of.

### Samples

**Problem Author: **Dmitry Gozman

**Problem Source: **Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007