Fibonacci System

时间限制:1s      空间限制:128MB

题目描述

Fib数列,大家都知道了.
F[0]=1
F[1]=1
F[2]=2
F[3]=3
F[4]=5
F[5]=8
现在我们将十进制的数,转成Fib进制,对于1到7可以分成下面形式
1=1F
2=10F
3=100F
4=101F
5=1000F
6=1001F
7=1010F
8=10000F
现在我们将转化出来的1和0构成的串,连在一起,对于上面数字1到7就成了110100101100010011010...
对于这样一个无限长的字符串,问前N个字符中有多少个1


输入格式

一个数字N,N < = 10^15


输出格式

前N个位置出现了多少个1


样例输入

3


样例输出

2

提示

没有写明提示


题目来源

没有写明来源