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

问题描述

裴波那契数列的前几个数为1，1，2，3，5，8，……，其规律为：
F1=1 (n=1)
F2=1 (n=2)
Fn=Fn-1+Fn-2 (n≥3)
也就是从第3项开始，每项都是前两项的和。编写程序求此数列的第n个裴波那契数。

输入格式

一个数整，表示要输出第n个裴波那契数

输出格式

一个整数，表示第n个裴波那契数。

样例输入

6

样例输出

8

数据规模和约定

30>=n>=1