题目描述

相信大家对之前dzw讲的递归写斐波那契印象深刻（shen wu tong jue）。今天让我们再来写一次斐波那契，我们知道第一位斐波那契数为$1$，第二位为$1$，第$n$位为$f[n]=f[n-1]+f[n-2]$,求第$x$位的斐波那契数。 答案对$10000000007$取模。 请使用scanf，printf代替cin，cout，因为输入量很大。

输入格式

输入一个$t$，表示询问的次数 之后$t$个$x$，求第$x$位的斐波那契数。

输出格式

对于每次询问，输出对应的斐波那契数。 答案对$10000000007$取模后输出

样例

输入

1
3

输出

2

数据范围与提示

$1 \leq t \leq 1000000$

$1 \leq x \leq 1000000$

(附，某大佬dzw提供的神秘公式 $(a+b) \% p = (a \% p + b \% p)\%p$)