Система Фибоначчи
Маленький Джон изучает числовые системы. После того как он все изучил о системах с фиксированным основанием, Джона заинтересовали другие, более необычные. Среди них он встретил систему Фибоначчи, которая однозначно представляет все натуральные числа при помощи двух цифр: единицы и нуля. Но в отличии от обычной бинарной системы, в системе Фибоначчи нельзя ставить две единицы в соседние позиции.
Можно доказать, что если имеется число в системе Фибоначчи, то его значение равно
N = a_n·F_n + a_{n-1}·F_{n-1} + ... + a_1·F_1,
где F_k - последовательность Фибоначчи, задаваемая соотношениями F_0 = F_1 = 1, F_i = F_{i-1} + F_{i-2}.
Например, первые несколько натуральных чисел имеют следующее представление в системе Фибоначчи:
1 = 1_F
2 = 10_F
3=100_F
4=101_F
5=1000_F
6=1001_F
7=1010_F
Джон записал очень длинную строку (считайте что бесконечную), состоящую из представлений последовательных натуральных чисел в системе Фибоначчи. Например, первыми цифрами такой строки будут 110100101100010011010...
Джона интересует, сколько раз встречается цифра 1 в N-ом префиксе строки. Напомним, что N-ым префиксом строки называется строка, состоящая из ее первых N символов.
Напишите программу, которая подсчитает количество цифр 1, которое встречается в N-ом префиксе строки Джона.
Входные данные
Одно целое число N (0 ≤ N ≤ 10^15).
Выходные данные
Вывести одно число - количество единиц в N-ом префиксе строки Джона.