Fibonacci Base

The Fibonacci base is a way to represent every natural number uniquely using only the digits 0 and 1.

When a natural number $N$ is written in Fibonacci base as $N = \overline{a_n a_{n-1} \cdots a_1}F$, its value is $N = a_n F_n + a{n-1} F_{n-1} + \cdots + a_1 F_1$. Here $F_k$ is the Fibonacci sequence defined by $F_0 = F_1 = 1$ and $F_i = F_{i-1} + F_{i-2}$. To make every representation unique, no two 1s may be adjacent in the Fibonacci base.

The following shows several natural numbers written in Fibonacci base.

$$1 = 1_F, \quad 2 = 10_F, \quad 3 = 100_F, \quad 4 = 101_F, \quad 5 = 1000_F, \quad 6 = 1001_F, \quad 7 = 1010_F$$

Now write the natural numbers $1, 2, 3, \cdots$ in Fibonacci base one after another, and concatenate all of the resulting strings. The beginning of the string built this way is 110100101100010011010$\cdots$.

Find how many 1s appear among the first $N$ characters of this string.

The first line contains an integer $N$. ($0 \le N \le 10^{15}$)

Print the number of 1s among the first $N$ characters of the concatenated string.