Неоднозначность по Фибоначчи
Как известно, в качестве базы для представления целых чисел в системе Фибоначчи взяты числа 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).
Выходные данные
Единственная строка - ответ здачи.