eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Неоднозначность по Фибоначчи

Неоднозначность по Фибоначчи

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Как известно, в качестве базы для представления целых чисел в системе Фибоначчи взяты числа 1, 2, 3, 5, 8, 13,21, 34, 55, 89, ... . Т.е. взяты подряд все т.н. числа Фибоначчи, начиная с F(2). Запись целого числа в этой системе представыляет собой двоичную комбинацию, в которой самый младший (правый) разряд соответствует числу 1, следующий – числу 2 и т.д. Единица означает, что соответствующий член базы вносит свою лепту (равную своей величине) в величинну данного числа, а 0 означает, что соответствующий элемент базы в данную запись числа свою лепту не вносит. Например, запись (101001)_f, обозначает число 1·1+0·2+0·3+1·5+0·8+1·13=19. Легко заметить, что в отличии от стандартной двоичной системы, в системе Фибоначчи представления чисел не однозначны. Например, приведенное выше число 19 в этой же системе можно записать и так (11111)_f.

Для заданного целого числа N определить количество его различных представлений в системе Фибоначчи.

Вхідні дані

Число N (-10^{7 }≤ N 10^7).

Вихідні дані

Единственная строка - ответ здачи.

Приклад

Вхідні дані #1
3
Вихідні дані #1
2
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь