该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

求菲波拉契数列的第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