题目描述

你们做过很多斐波那契数列了，但是都很小，现在来个大的。给你一个整数 $x$，求斐波那契数列第 $x$ 项。由于结果很大，请输出该结果除以 $10^9+7$ 的余数。

输入格式

第一行一个整数 $T$ 表示测试数据的组数。$T$ 不超过 $10^5$。

接下来 $T$ 行每行一个数字，表示待求的项。该数字不超过 $10^{18}$。

输出格式

对每组输入，输出其运算结果。

5
1
2
3
4
999999999999999999

1
1
2
3
470273943