菲波那契数列

内存限制：256 MB 时间限制：1000 ms

菲波那契数列是指这样的数列：

$f(1)=f(2)=1$

$f(n)=f(n-1)+f(n-2)$，$n \ge 3$

给出一个正整数 $k$，求 $f(k)$。

输入一行，包含一个正整数 $k$。（$1 ≤ k ≤ 40$）

输出一行，包含一个正整数，表示菲波那契数列中第 $k$ 个数的大小。

样例输入 1

样例输出 1