题目描述

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、...

在数学上，斐波纳契数列以如下被以递归的方法定义： $F_0=0$，$F_1=1$，$F_n=F_{(n-1)}+F_{(n-2)}$（ $n \gt 2，n \in$自然数 ）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

给定一个整数 n ，求斐波那契数列第 n 项是多少？

输入格式

1 个整数 n ：范围在 [1,30]。

输出格式

1个整数

样例

6

8

样例解释

注：本练习要求不得使用数组。