Зоны на плоскости

Рассмотрим зоны z_i на плоскости, состоящие из треугольников. Первая зона z_1 состоит из двух прямоугольных равнобедренных треугольников, образующих квадрат. Зона z_{n+1} получается из зоны z_{n }так: на катетах каждого треугольника из зоны z_n строятся два равнобедренных прямоугольных треугольника. Если при этом новый треугольник попадает в зону с меньшим номером, то он не берется. Объединение получившихся треугольников и составляет зону z_{n+1}.

Ваша задача - найти количество простых многоугольников, из которых состоит зона z_n.

Входные данные

Во входном файле записано число n (1 ≤ n ≤ 2000).

Выходные данные

В выходной файл выведите единственное число - количество простых многоугольников, из которых состоит зона z_n.

Примеры