题目描述

斐波那契数列的前两项都是 1，从第三项开始，每一项都等于前两项之和。

1, 1, 2, 3, 5, 8, ...

输入一个整数 n，输出斐波那契数列的第 n 项。

输入格式

输入一个整数 n。

输出格式

输出一个整数，表示第 n 项的值。

样例输入

6

样例输出

8

数据范围

1 <= n <= 45