题目描述

斐波那契数列是一个特殊的数列：

1,1,2,3,5,8,13,21,34,55,……

数列的第一项和第二项都是 1，从第三项开始，每一项是其前面两项之和。

输入正整数 n，编程输出该数列的第 n 项。

输入格式

一个整数 n。

输出格式

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

输入样例 #1

50

输出样例 #1

12586269025

输入样例 #2

1

输出样例 #2

1

输入样例 #3

2

输出样例 #3

1

数据范围与约定

1≤n≤50。