Золото дядечка Скруджа
Дядечко Скрудж виготовив безліч золотих злитків і пронумерував їх послідовностями з нулів і одиниць довжини 2n - 2 (номер кожного злитка вибитий на ньому). Відомо, що:
Будь-які два злитки мають різні номери.
У номері будь-якого з злитків не зустрічається двох нулів підряд.
Для будь-якої послідовності, що відповідає властивості 2, злиток з таким номером є в колекції дядечка Скруджа.
Потім дядечко Скрудж вирішив розкласти злитки по сейфах. Коди до сейфів підібрані схожим чином з номерами злитків. А саме:
Код до сейфу є послідовністю з нулів і одиниць довжини n - 2.
Коди до будь-яких двох сейфів різняться.
У коді жодного з сейфів не зустрічається двох нулів підряд.
Для будь-якого коду, що відповідає властивостям 1 і 3, сейф з таким кодом стоїть у сховищі дядечка Скруджа.
Дядечко Скрудж поклав у кожен з сейфів однакову кількість золотих злитків, а залишені злитки (їх залишилося менше, ніж сейфів) вирішив відправити на благодійність. Знайдіть, скільки злитків лежить у кожному з сейфів дядечка Скруджа.
Вхідні дані
Ціле число n (3 ≤ n ≤ 70000).
Вихідні дані
Виведіть кількість злитків у кожному з сейфів.