题目描述

斐波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

给出一个正整数a，要求菲波那契数列中第a个数是多少。

输入格式

输入一个数字n，代表第n个数字

输出格式

输出一行，为斐波那契数列第n项的值

输入输出样例 #1

输入 #1

3

输出 #1

2

输入 #2

19

输出 #2

4181