10430 - 斐波那契数列（高精）

Input

输入1个数 n(1 \leq n \leq 30000)。

Output

输出 F(n)。

Examples

Input

5

Output

5

Input

1000

Output

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Time Limit 1000 毫秒
Memory Limit 128 MB
Stats
上一题 下一题