求斐波那契数列的第 $n$ 项。
斐波那契数列：$1、1、2、3、5 …$，这个数列从第 $3$ 项开始，每一项都等于前两项之和。
$$f(n)= \begin{cases} 1& n \le 2\\ f(n-1)+f(n-2)& \text{n>2} \end{cases}$$
输入格式
共一行，包含整数 $n$。
输出格式
共一行，包含一个整数，表示斐波那契数列的第 $n$ 项。
数据范围
$1 \le n \le 30$
样例输入
4
样例输出
3
求斐波那契数列的第 $n$ 项。
斐波那契数列：$1、1、2、3、5 …$，这个数列从第 $3$ 项开始，每一项都等于前两项之和。
$$f(n)= \begin{cases} 1& n \le 2\\ f(n-1)+f(n-2)& \text{n>2} \end{cases}$$
输入格式
共一行，包含整数 $n$。
输出格式
共一行，包含一个整数，表示斐波那契数列的第 $n$ 项。
数据范围
$1 \le n \le 30$
样例输入
4
样例输出
3
