B. Bespread with chequers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

JYH有一个 $$$2$$$ 行,但列数不定的棋盘，他邀请你在他的棋盘上堆满棋子。

你带了一个神奇口袋，里面装着无穷多的 $$$1\times 2$$$ 大小和 $$$2\times 2$$$ 大小的棋子，其中 $$$1\times 2$$$ 大小的棋子可以横着占据 $$$1$$$ 行 $$$2$$$ 列的格子，也可以竖着占据 $$$2$$$ 行 $$$1$$$ 列的格子。

JYH想跟你玩 $$$T$$$ 次游戏，每次游戏他会告诉你当前棋盘的列数 $$$n$$$ ,请你对于每次游戏输出铺满当前棋盘的方案总数。

由于方案总数可能很大，请你输出方案总数对 $$$10^9+7$$$ 取模后的值。

Input

第一行输入一个整数 $$$T$$$ ($$$1\leq T \leq 10^3$$$)，表示游戏次数。

接下来 $$$T$$$ 行每行一个整数 $$$n$$$ ($$$1\leq n \leq 10^6$$$)，表示当前棋盘的列数。

Output

对于每次游戏输出一行一个整数，表示铺满当前棋盘的方案总数对 $$$10^9+7$$$ 取模后的值。

Example
Input
5
1
3
4
2
6
Output
1
5
11
3
43
Note

下图为 $$$n=3$$$ 时对应的可能的铺棋子方案。

B.png