Зони на площині#4960
Розглянемо зони z_i на площині, які складаються з трикутників. Перша зона z_1 складається з двох прямокутних рівнобедрених трикутників, які утворюють квадрат. Зона z_{n+1} отримується із зони z_n так: на катетах кожного трикутника із зони z_n будуються два рівнобедрених прямокутних трикутники. Якщо при цьому новий трикутник попадає у зону з меншим номером, то він не береться. Об'єднання отриманих трикутників і складає зону z_{n+1}.
Ваша задача — знайти кількість простих багатокутників, з яких складається зона z_n.
У вхідному файлі записано число (1 \leq n \leq 2000).
У вихідний файл виведіть єдине число — кількість простих багатокутників, з яких складається зона z_n.
Приклад 1