题目背景

菲波那契数列是指这样的数列：数列的第一项和第二个项都为 $1$，接下来每项都等于前面两项之和。

题目描述

输入一系列整数 $n_i$，计算菲波那契数列第 $n_i$ 项的值。由于有些项的值很大，只需要输出每项 %123456 的结果即可。

输入格式

一行，若干正整数 $n_i$，相邻整数间用一个空格隔开。

输出格式

若干行，就是输入的每个正整数对应的菲波那契数列第 $n_i$ 项的值 %123456 的结果。

输入输出样例

5 2 19 1

5
1
4181
1

说明/提示

👀️ 对于$100\%$ 的数据，$1 \leq n_i \leq 1000000$。

😕 注意，本题没有告知输入的正整数的数量！