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.
There is a single integer n (1 ≤ n ≤ 2000) on the first line
of the input.
Output a single number — the number of simple polygons zone zn
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007