题目描述

$Fibonacci$ 数列是一个特殊的数列：数列的第一项和第二项分别为 0 和 1 ，从第三项开始，每一项是其前面两项之和。即 0，1，1，2，3，5，8，....…。请编程读入一个整数 $n$ ，然后输出该数列的第 $n$ 项。

输入格式

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

输出格式

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

样例

19

2584