У вас есть n детских игрушечных кубиков. Вы хотите построить из них крепость.
Крепость — это последовательность из башен, составленных из кубиков. При этом в каждой башне может быть только нечетное число кубиков.
Ваша задача — посчитать количество крепостей, которые можно составить ровно из n кубиков. Две крепости считаются различными, если существует такое i, что количество кубиков в i-ой слева башне первой крепости отличается от количества кубиков в i-ой слева башне второй крепости.
В первой строке записано целое число n (1 ≤ n ≤ 70).
Выведите количество крепостей, которые можно составить ровно из n кубиков.
Обратите внимание, что ответ может не помещаться в 32-битный знаковый тип.
1
1
2
1
4
3
10
55
