Fibonacci System#5559

Fibonacci System

5 seconds

64 megabytes

Medium

Little John studies numeral systems. After learning all about fixed-base systems, he became interested in more unusual cases. Among those cases he found a Fibonacci system, which represents all natural numbers in a unique way using only two digits: zero and one. But unlike a usual binary notation, in the Fibonacci system you are not allowed to place two $1$ 's in adjacent positions.

One can prove that if you have a number in Fibonacci system, its value is equal to

$N = a_{n} \cdot F_{n} + a_{n - 1} \cdot F_{n - 1} + \dots + a_{1} \cdot F_{1}$ N = a_n \cdot F_n + a_{n-1} \cdot F_{n-1} + \ldots + a_1 \cdot F_1,

where $F_{k}$ F_k is the usual Fibonacci sequence defined by $F_{0} = F_{1} = 1$ F_0 = F_1 = 1, $F_{i} = F_{i - 1} + F_{i - 2}$ F_i = F_{i-1} + F_{i-2}.

For example, the first few natural numbers have the following unique representations in the Fibonacci system:

$1 = 1_{F}$ 1 = 1_F

$2 = 1 0_{F}$ 2 = 10_F

$3 = 10 0_{F}$ 3 = 100_F

$4 = 10 1_{F}$ 4 = 101_F

$5 = 100 0_{F}$ 5 = 1000_F

$6 = 100 1_{F}$ 6 = 1001_F

$7 = 101 0_{F}$ 7 = 1010_F

John wrote a very long string (consider it infinite) consisting of consecutive representations of natural numbers in the Fibonacci system. For example, the first few digits of this string are $110100101100010011010...$

He is very interested in how many times the digit $1$ occurs in the $N$ -th prefix of the string. Remember that the $N$ -th prefix of the string is the string consisting of its first $N$ characters.

Write a program which determines how many times the digit $1$ occurs in the $N$ -th prefix of John's string.

Input

The input contains a single integer $N$ ( $0 \leq N \leq 1 0^{15}$ 0 \leq N \leq 10^{15}).

Output

Output a single integer—the number of $1$ 's in the $N$ -th prefix of John's string.

Examples

Example 1

Loading

N = a_{n} \cdot F_{n} + a_{n - 1} \cdot F_{n - 1} + \dots + a_{1} \cdot F_{1}

F_{k}

F_{0} = F_{1} = 1

F_{i} = F_{i - 1} + F_{i - 2}

1 = 1_{F}

2 = 1 0_{F}

3 = 10 0_{F}

4 = 10 1_{F}

5 = 100 0_{F}

6 = 100 1_{F}

7 = 101 0_{F}

0 \leq N \leq 1 0^{15}