## Fibonacci Sequence

View as PDF

Points: 0.76 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Anh Hiếu
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Fibonacci sequence is defined as follow: ~F_{1} = 1~, ~F_{2} = 2~, ~F_{i} = F_{i - 1} + F_{i - 2}~ ~(i > 2)~.

Each natural number ~X~ can be expressed by the maximum numbers that are less than or equal to ~X~ in Fibonacci sequence: ~X = a_{1} \cdot F_{1} + a_{2}\cdot F_{2} + \dots~ Therefore, in Fibonacci system, ~X~ is known as: ~a_{n} a_{n - 1} \dots a_{1}~. For example, ~1 = 1_{F}~, ~2 = 10_{F}~, etc. If we write all natural numbers successively in Fibonacci system, we will obtain a sequence like this: 1_1_0 ...This is called "Fibonacci bit sequence of natural numbers".

Your task is counting the numbers of times that bit ~1~ appears in the first ~N~ bits of this sequence.

#### Input

Line ~1~: An integer ~N~ ~(1 \le N \le 10^{15})~

#### Output

Line ~1~: An integer ~K~ is the result

#### Sample Input

2


#### Sample Output

2