И снова 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.