ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Дядюшка Скрудж изготовил множество золотых слитков и пронумеровал их последовательностями из нулей и единиц длины 2N-2 (номер каждого слитка выбит на нём). Известно, что
  1. Любые два слитка имеют различные номера.
  2. В номере любого из слитков не встречается двух нулей подряд.
  3. Для любой последовательности, отвечающей свойству 2, слиток с таким номером есть в коллекции дядюшки Скруджа.
Затем дядюшка Скрудж решил разложить слитки по сейфам. Коды к сейфам подобраны схожим образом с номерами слитков. А именно
  1. Код к сейфу является последовательностью из нулей и единиц длины N-2.
  2. Коды к любым двум сейфам различаются.
  3. В коде ни одного из сейфов не встречается двух нулей подряд.
  4. Для любого кода, отвечающего свойствам 1 и 3, сейф с таким кодом стоит в хранилище дядюшки Скруджа.
Дядюшка Скрудж положил в каждый из сейфов одинаковое количество золотых слитков, а оставшиеся слитки (их осталось меньше, чем сейфов) решил отправить на благотворительность. Найдите, сколько слитков лежит в каждом из сейфов дядюшки Скруджа.

Исходные данные

Целое число 3 ≤ N ≤ 70000.

Результат

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

Пример

исходные данныерезультат
3
4
Автор задачи: Александр Ипатов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2006