题目描述

斐波那契数列是这样一个数列：

它的第 $1$ 项是 $0$，第 $2$ 项是 $1$。

接下来的第 i 项 则为第 i-1 项与 第 i-2 项之和。

因此斐波那契数列的前几项为：$0, 1, 1, 2, 3, 5, 8, 13, \cdots$

请输出斐波那契数列第 $n$ 项。

输入格式

输入一个正整数 $n$，表示要求斐波那契数列的第 $n$ 项。

输出格式

输出斐波那契数列第 $n$ 项的值。

样例

4

2

提示

$1 \leq n \leq 15$