SPFIBO - Fibonacci Sequence

Fibonacci sequence is defined as follow: F1 = 1, F2 = 2, Fi = Fi-1 + Fi-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 = a1xF1 + a2xF2 + … Therefore, in Fibonacci system, X is known as: anan-1…a1. For example, 1 = 1F, 2 = 10F, 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 <= N <= 1015)

Output

Line 1: An integer K is the result

Example

Input:
2

Output:
2

Được gửi lên bởi:HNUE
Ngày:2010-11-16
Thời gian chạy:0.102s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Anh Hiếu

hide comments
2019-09-02 05:58:43


Last edit: 2019-09-02 05:58:59
2015-06-18 01:28:25 Stupid Dog
I like Vietnamese
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.