SP7891 SPFIBO - Fibonacci Sequence

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} $ xF $ _{1} $ + a $ _{2} $ xF $ _{2} $ + … Therefore, in Fibonacci system, X is known as: a $ _{n} $ a $ _{n-1} $ …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.

Line 1: An integer N (1

Line 1: An integer K is the result