Description

如果设F(n)为该数列的第n项（n∈N+）。那么斐波那契数列就可以写成如下形式：   F(1) = 1，F(2)=1，F(n)=F(n-1)+F(n-2) (n≥3) 比如斐波那契数列的前几项：1、1、2、3、5、8、13、21

Input

计算斐波那契数列的第N项(1 <= N <= 48)

Output

斐波那契数列的第N项

Samples

5

5