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}$)

출력

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

제한

힌트