Zones on a Plane#4960
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 part of a zone with a lower number. The remaining triangles constitute zone z_{n+1}.
Given an integer , find how many simple polygons constitute zone z_n.
There is a single integer (1 \leq n \leq 2000) on the first line of the input.
Output a single number — the number of simple polygons zone z_n consists of.
Example 1