背景

黑塔：博识学会吗，只是有些人有点意思罢了，要我说，那的大部分人纯粹就是冗余，你应该懂得怎么利用空间的吧，小灰毛？

描述

请你求出斐波那契数列第a[i]项。

格式

输入

给出若干行输入，每行包括一个a[i]，表示求斐波那契数列第a[i]项。

输出

包括若干行，第 i 行表示斐波那契数列第a[i]项的值（最后一行没有换行，行末没有多余的空格）。

样例

1
2
3

1
1
2

数据范围

对于 100% 的数据，1≤i≤1×10⁶，1≤a[i]≤90。

时间限制

200ms

内存限制

1MB

提示

螺丝咕姆：请您注意时间和格式。