Consider zones z_i on a plane which consist of triangles. Zone z₁ 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.