该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

定义：

f(1)=1,

f(2)=1

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

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

输入格式

输入包含多组测试数据。

每组数据为一个正整数$\red{n}$。

输出格式

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

样例

输入数据

100

输出数据

354224848179261915075