A. Крепость
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У вас есть n детских игрушечных кубиков. Вы хотите построить из них крепость.

Крепость — это последовательность из башен, составленных из кубиков. При этом в каждой башне может быть только нечетное число кубиков.

Ваша задача — посчитать количество крепостей, которые можно составить ровно из n кубиков. Две крепости считаются различными, если существует такое i, что количество кубиков в i-ой слева башне первой крепости отличается от количества кубиков в i-ой слева башне второй крепости.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 70).

Выходные данные

Выведите количество крепостей, которые можно составить ровно из n кубиков.

Обратите внимание, что ответ может не помещаться в 32-битный знаковый тип.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
1
Входные данные
4
Выходные данные
3
Входные данные
10
Выходные данные
55