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