斐波那契数列

题目描述

上会提到，YAO错误的理解了斐波那契数列，Orange纠正了YAO的想法，YAO现在理解了正确的斐波那契数列定义，现在她想来考考你，斐波那契数列的第 $x$ 项是多少？

YAO会给你 $T$ 个询问，每次包含一个整数 $x$，你需要告诉她斐波那契数列的第 $x$ 项是多少？

由于这个数可能很大，请对 $10^9 + 7$ 取MOD。

输入格式

第一行一个整数 $T$，表示YAO的提问次数。

随后 $T$ 行，每行一个整数 $x$，表示询问。

数据范围

$1 \le T,x \le 5 \times 10^6$

输出格式

对于每个询问，给出答案。

样例 #1

样例输入 #1

3
1
2
3

样例输出 #1

1
1
2