2008 - 前4项和

通过次数

22

提交次数

54

时间限制 : 1 秒
内存限制 : 128 MB

已知:

F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, 

F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)。

给出一个n,求F(n)

输入

输入一个n(1<=n<=10^4)

输出

输出F(n)

样例

输入

100

输出

4203968145672990846840663646