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