入门⏱ 1000ms💾 256MB#P2239🏷️ 数学递推

题目描述

蜂巢里的蜂王有一个繁殖规律:第 $1$ 代和第 $2$ 代的蜜蜂数都是 $1$, 从第 $3$ 代起,每一代的蜜蜂数等于前两代之和。

求第 $k$ 代的蜜蜂数。

输入格式

一行,一个正整数 $k$。

输出格式

一行,一个正整数:第 $k$ 代的蜜蜂数。

数据范围

$$1 \le k \le 46$$

样例输入 #1
19
样例输出 #1
4181
样例输入 #2
1
样例输出 #2
1