题目描述

定义：

f(1)=1, f(2)=1

f(n>2)=f(n-1)+f(n-2)

我们把符合以上定义的序列称为斐波那契序列，现在给你一个数字$n$，请你求出$f(n)$。

输入样例

一个正整数$n$。

输出样例

输出对应的$f(n)$。题目保证结果不会超过$50000$位数字。

样例输入

100

样例输出

354224848179261915075