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.
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 z_n consists of.