Древний календарь

Недавно Вася прочитал статью о том, что берляндские ученые обнаружили древний календарь исчезнувшей цивилизации туземцев апрелья, который, как и многие другие древние календари, предсказывал не столь далекий конец света.

Календарь туземцы создали, опираясь на свои священные числа. Нулевым священным числом была единица, первым --- тоже единица, а каждое следующее священное число $F_i$ вычислялось как сумма двух предыдущих: $F_i = F_{i-1} + F_{i-2}$. Каждое натуральное число в календаре представлялось в виде суммы некоторых чисел $F_i, i > 0$ таким образом, что если в сумме присутсвовало некоторое $F_j$, то ни $F_{j-1}$, ни $F_{j+1}$ в разложении не присутствовало. В такой системе счисления, например, число $16$ имело вид $100100$, так как $16 = 1 \cdot 13 + 0 \cdot 8 + 0 \cdot 5 + 1 \cdot 3 + 0 \cdot 2 + 0 \cdot 1$. Затем все числа, записанные таким образом, последовательно перенесли на календарь, начиная с единицы. Если обозначить запись числа $i$ в описанной системе счисления как $f\{i\}$, то календарь представляет собой строку $S = f\{1\}f\{2\}f\{3\}\dots$, состояющую из записей $f\{i\}$ всех натуральных чисел.

А вас Вася просит определить, сколько групп из двух подряд идущих нулей находится в промежутке с первого символа календаря по $N$-й символ.

Во входном файле содержится единственное число $N$ ($1 \le N \le 10^{18}$) --- номер последнего символа, который интересен Васе.

В выходной файл выведите единственное число --- количество вхождений групп из двух подряд идущих нулей среди первых $N$ символов календаря.

Первые $20$ символов календаря ---$11010010110001001101$.