题目描述

斐波那契数列是满足如下性质的一个数列：

• $f(1) = 1$
• $f(2) = 1$
• $f(n) = f(n-1) + f(n-2)$ ( $n \ge 3$ 且 $n$ 为整数 )

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为 $1$，接下来每个数都等于前面 $2$ 个数之和。

给出一个正整数 $k$，要求菲波那契数列中第 $k$ 个数是多少。

输入格式

一个非负整数，$k$

输出格式

斐波那契数列第 $k$ 项的值。

样例

样例输入

4

样例输出

3

数据范围与提示

$n \leq 90$

有一种小兔子，出生后一个月就可以长大成熟，然后再过一个月一对成熟的兔子就可以生育成一对小兔子，且以后每个月都能生育一对。 现在，我们有一对刚出生的小兔子，那么，10个月以后会有多少对这样子的兔子呢？假设所有兔子都不会死亡。