时间限制:1000ms  空间限制:256MB

题目描述

斐波拉契数列,又称黄金分割数列,因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3）。

斐波拉契数列的前两项分别为1,1。以后每项为前两项之和。现在输入n,要求斐波拉契数列前n项的和(1<=n<=5000)。

输入格式

输入只有一个数n，表示求斐波拉契数列前n项的和。

输出格式

输出斐波拉契数列前n项的和

样例

输入#1

3

输出#1

4

数据范围/约定

对于40%的数据，n<=10

对于100%的数据，n<=5000