29435번 - Последовательность Фибоначчи 다국어

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

Числа Фибоначчи --- это последовательность целых чисел, заданная рекуррентным соотношением: $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}$)

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