eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Золото дядюшки Скруджа

Золото дядюшки Скруджа

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дядюшка Скрудж изготовил множество золотых слитков и пронумеровал их последовательностями из нулей и единиц длины 2n - 2 (номер каждого слитка выбит на нём). Известно, что

  1. Любые два слитка имеют различные номера.

  2. В номере любого из слитков не встречается двух нулей подряд.

  3. Для любой последовательности, отвечающей свойству 2, слиток с таким номером есть в коллекции дядюшки Скруджа.

Затем дядюшка Скрудж решил разложить слитки по сейфам. Коды к сейфам подобраны схожим образом с номерами слитков. А именно

  1. Код к сейфу является последовательностью из нулей и единиц длины n - 2.

  2. Коды к любым двум сейфам различаются.

  3. В коде ни одного из сейфов не встречается двух нулей подряд.

  4. Для любого кода, отвечающего свойствам 1 и 3, сейф с таким кодом стоит в хранилище дядюшки Скруджа.

Дядюшка Скрудж положил в каждый из сейфов одинаковое количество золотых слитков, а оставшиеся слитки (их осталось меньше, чем сейфов) решил отправить на благотворительность. Найдите, сколько слитков лежит в каждом из сейфов дядюшки Скруджа.

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

Целое число n (3n70000).

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

Выведите количество слитков в каждом из сейфов.

Пример

Входные данные #1
3
Выходные данные #1
4
Автор Александр Ипатов
Источник 2006 Ural SU Contest, Петрозаводск, Зима, Январь 30, Задача D