#NC22160. 牛牛学数列5

牛牛学数列5

题目描述

牛牛开始学习数列啦。现定义斐波那契数列,其前两项为 F1=1,F2=1F_1=1,F_2=1,对于 n≥3n\ge3,有:

Fn=Fn−1+Fn−2.F_n=F_{n-1}+F_{n-2}.

请计算并输出第 nn 项 FnF_n 的值。

输入格式

在一行中输入一个整数 nn。当前离线题包的输入范围为 1≤n≤901\le n\le90。

输出格式

输出一个整数,表示斐波那契数列的第 nn 项 FnF_n。

提示

数列前几项为 1,1,2,3,5,81,1,2,3,5,8,因此 F6=8F_6=8。

样例 1

2
1

样例 2

6
8

来源

牛客原题