题目描述

斐波那契数列的定义为：

$$\begin{cases} F_1 = 1 \\ F_2 = 1 \\ F_n = F_{n-1} + F_{n-2}, \quad n \geq 3 \end{cases} $$

给定整数 $n$，求 $F_n$。

输入格式

输入包含一个整数 $n$ ($1 \leq n \leq 30$)。

输出格式

输出一个整数—斐波那契数列的第 $n$ 项。

样例

2

1

6

8