问题描述

斐波那契数列定义如下：

• $F_1 = 1$
• $F_2 = 1$
• $F_n = F_{n-1} + F_{n-2}$（$n \ge 3$）

给定一个正整数 $n$，求出 $F_n$。

换句话说便是数组的第一项和第二项的值为 $1$，剩下的每一项都是前两项之和。

输入格式

一行一个整数 $n$。

输出格式

输出一行一个整数，表示 $F_n$。

样例输入 1

1

样例输出 1

1

样例输入 2

5

样例输出 2

5

样例输入 3

30

样例输出 3

832040

评测数据规模

• $1 \le n \le 30$