1499. Gauss And Fibonacci

单点时限: 2.0 sec

内存限制: 256 MB

We all know that 1+2+…+n=(1+n)*n/2;Gauss worked it out when he was a child!

And we also know the famous number sequence 1,1,2,3,5,8,13… named Fibonacci sequence.(F(1)=F(2)=1;when n>2,F(n)=F(n-1)+F(n-2);)

If we put them togather,what thing will happen?

输入格式

The input will consist of a series of integers N, one integer per line.Process to end of file.(0<N<1000000000)

输出格式

For each case,calculate the sum of the Fibonacci numbers who’s sequence number is not bigger than N.Since it can be very huge,you should onle output the last eight digits,do not output leading zeros(if the answer is 02007729,just output 2007729).

样例

Input
6
Output
20
Hint:
1+1+2+3+5+8=20

42 人解决,80 人已尝试。

49 份提交通过,共有 188 份提交。

7.7 EMB 奖励。

创建: 12 年,5 月前.

修改: 2 年,3 月前.

最后提交: 5 月,4 周前.

来源: N/A

题目标签