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

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

Календарь туземцы создали, опираясь на свои священные числа. Нулевым священным числом была единица, первым --- тоже единица, а каждое следующее священное число $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$.