背景

月雪宫子同学，训练有素的Rabbit小队队长，因为夏天、大海和令她自信的装束而飘飘然了！

为了调查虾神秘失踪的原因，Rabbit小队来到海边调查！在孤岛上遇见的一窝兔子引发了宫子同学的遐想，她假设最初来到孤岛的一对兔子恰为夫妇。接下来，每一对兔子自出生的第二个月起诞下一对兔子……

宫子同学很好奇，若干月过后，在孤岛上会有多少对兔子呢？

题目描述

眼熟的数列？

兔子对数预计变化：

1，1，2，3，5，8，13，21……

而聪慧的你听闻宫子同学的疑惑，认为题解信手拈来！不过这一次，你要挑战自我，选择高难度的解法！

自我调用！

是时候展现真正的技术了！

必须使用递归方法求解，不使用递归方法得到的题解将被手动判零。

Format

Input

宫子同学向你发出疑问！

卑力亦如兔子的数目劲增！

输入包含一个正整数$n$，意味着宫子同学正好奇第$n$个月时的兔子对数。

第一对兔子进入岛屿时视作第0个月！

Output

答案显而易见！

输出包含一个正整数，即是第$n$个月时的兔子对数。

Samples

5

8

Limitation

1s, 1024KiB for each test case.

对于100%的数据，满足$n \leq 90$

宽松的格式检查~

不必拘泥于那几个空格和回车。

“放松，朋友！多一点少一点没什么关系！”

✩被你找到啦✩

优化提示

使用常规的递归方法会导致时间和内存溢出！

亲自遍历程序的运行过程，似乎有严重的算力浪费！

把已经计算完毕的值用什么东西存起来，从而避免反复运算，会不会好一些呢？

像你这样的大人……