피보나치 자릿수

Вася --- юный математик. Недавно на занятиях он узнал про числа Фибоначчи.

Числа Фибоначчи --- это последовательность целых чисел, заданная рекуррентным соотношением: $F\_0 = 1$, $F\_1 = 1$, $F\_n = F\_{n - 1} + F\_{n - 2}$, $n \ge 2$.

Сегодня в математическом журнале он прочитал, что каждое натуральное число представимо в системе счисления Фибоначчи. Число $M$ в фибоначчиевой системе счисления представляется последовательностью битов $\overline{a\_k \ldots a\_1}$ ($a\_i \in \lbrace 0, 1\rbrace$), такой что $M = a\_k \cdot F\_k + \ldots + a\_1 \cdot F\_1$. Заметим, что число в таком виде представляется не единственным способом, поэтому среди всех последовательностей выберем самую длинную, а среди всех самых длинных выберем лексикографически наибольшую. Например, $5 = 1000\_F$, $7 = 1010\_F$, $2 = 10\_F$.

Напомним, что последовательность $a\_1 \ldots a\_k$ лексикографически больше последовательности $b\_1 \ldots b\_l$, если существует такое $i \le min\lbrace k, l \rbrace$, что $a\_j = b\_j$, если $j < i$, и $a\_i > b\_i$.

Пусть $S$ --- это строка из последовательно записанных натуральных чисел в фибоначчиевой системе счисления. $S = 1101001011000100110101000010001 \ldots$ После прочтения Васю заинтересовал вопрос: часто ли в строке $S$ встречаются две единицы подряд?

Вам задано число $N$, требуется найти количество вхождений строки <<$11$>> в префикс длины $N$ строки $S$.

Входной файл содержит единственное целое число $N$ ($1 \le N \le 10^{18}$)

В выходной файл выведите одно целое число: ответ на задачу.