І знову 3x+1
Проблема 3x+1 добре відома в математичних колах і зрозуміла навіть школярам. Візьмемо будь-яке натуральне число. Якщо воно парне, ділимо його на 2, а якщо непарне, то множимо на 3 і додаємо 1. З отриманим числом повторюємо процес. І так далі...
Наприклад, взявши число 5, отримаємо послідовність:
5 (*3+1) 16 (/2) 8 (/2) 4 (/2) 2 (/2) 1 (*3+1) 4... цикл замкнувся (1-4-2).
Яке б натуральне число ми не взяли, врешті-решт перетворення завжди зведуться до 1. Строго кажучи, це твердження доведено лише для чисел, що не перевищують 19-ти розрядні числа, але в рамках цього завдання суворе математичне доведення не потрібне.
Ваше завдання - підрахувати, скільки існує натуральних чисел, з яких при перетвореннях до 1 утворюються ланцюжки довжиною N. При цьому цикл 1-4-2 не повинен входити в ланцюжок, тобто ланцюжок 1-4-2-1 не є коректним ланцюжком довжиною 4.
Зазначений вище ланцюжок 5-16-8-4-2-1 має довжину 5.
Вхідні дані
Єдиний рядок вхідних даних містить одне натуральне число N (1 ≤ N ≤ 62).
Вихідні дані
Єдиний рядок вихідних даних повинен містити одне натуральне число - кількість чисел, що утворюють ланцюжки довжиною N.