题目描述

斐波那契数列：斐波那契数列（Fibonacci）是指这样的数列：1，1，2，3，5，8，13……这个数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。请你设计一个程序，当输入正整数n，输出斐波那契数列第n项

输入格式

一个正整数n，表示第n项

输出格式

第n项是多少

样例

输入样例 1

2

输出样例 1

1

输入样例 2

5

输出样例 2

5

输入样例 3

20

输出样例 3

6765