题目描述

斐波那契数列的通项公式：

f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) 【当n>=3时】

现输入一个数n,请计算出第n项斐波那契数f(n)的值

输入格式

输入一个正整数n

输出格式

输出f(n)

样例1

输入

1

输出

1

样例2

输入

10

输出

55

数据规模与约定

n<=40