피보나치 진법

피보나치 진법은 0과 1만으로 모든 자연수를 유일하게 나타내는 방법이다.

자연수 $N$을 피보나치 진법으로 $N = \overline{a_n a_{n-1} \cdots a_1}_F$ 와 같이 나타내면, 그 값은 $N = a_n F_n + a_{n-1} F_{n-1} + \cdots + a_1 F_1$ 이다. 여기서 $F_k$는 피보나치 수열로 $F_0 = F_1 = 1$, $F_i = F_{i-1} + F_{i-2}$ 로 정의된다. 각 자연수를 유일하게 나타내기 위해, 피보나치 진법에서는 두 개의 1이 서로 인접할 수 없다.

다음은 몇몇 자연수를 피보나치 진법으로 나타낸 것이다.

$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$

이제 자연수 $1, 2, 3, \cdots$ 를 차례대로 피보나치 진법으로 나타낸 뒤, 그 결과 문자열을 모두 이어 붙이자. 그러면 만들어지는 문자열의 앞부분은 110100101100010011010$\cdots$ 이 된다.

이 문자열의 처음 $N$글자 중에 1이 몇 개 있는지 구하여라.

첫째 줄에 정수 $N$이 주어진다. ($0 \le N \le 10^{15}$)

이어 붙인 문자열의 처음 $N$글자에 들어 있는 1의 개수를 출력한다.