说明

求菲波拉契数列的第n位。    菲波拉契数列：$a1=1，a2=1，a3=a1+a2，an=a(n-1)+a(n-2)$ 如：1 1 2 3 5 8 13 21 ……

输入格式

一个整数n（n<=1000)

输出格式

第n项的数值。

样例

500

139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125