# 1499. Gauss And Fibonacci

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


43 人解决，81 人已尝试。

50 份提交通过，共有 190 份提交。

5.2 EMB 奖励。