Зони на площині

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

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

Вхідні дані

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

Вихідні дані

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

Приклади