\begin{problem}{Последовательность Фибоначчи}{fibseq.in}{fibseq.out}{2 секунды}

%Автор задачи: Нияз Нигматуллин
%Автор условия: Нияз Нигматуллин

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

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


\InputFile

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

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

\Examples
\begin{example}%
\exmp{
3
}{
1
}%
\exmp{
10
}{
2
}%
\end{example}

\Note
Решения, работающие при $N \le 5000$ будут оцениваться из $20$ баллов.

Решения, работающие при $N \le 10^7$ будут оцениваться из $60$ баллов.

\end{problem}
