2081: 神奇口袋
[Creator : ]
Description
Wangy 有一个 2 行, 但列数不定的棋盘，他邀请小S在他的棋盘上堆满棋子。 小S带了一个神奇口袋，里面装着无穷多的 1 × 2 大小和 2 × 2 大小的矩形棋子，其中 1 × 2 大小的棋子可以横
着占据 1 行 2 列的格子，也可以竖着占据 2 行 1 列的格子。Wangy 想跟小S玩 T 次游戏，每次游戏他会告诉小S当前棋盘的列数 n , 可是小S急于找学妹讲题，所以请你对于每次游戏输出铺满当前棋盘的方案总数。
由于方案总数可能很大，请你输出方案总数对 109 + 7 取模后的值。
由于方案总数可能很大，请你输出方案总数对 109 + 7 取模后的值。
Input
第一行输入一个整数 T (1 ≤ T ≤ 103 )，表示游戏次数。
接下来 T 行每行一个整数 n (1 ≤ n ≤ 106 )，表示当前棋盘的列数。
接下来 T 行每行一个整数 n (1 ≤ n ≤ 106 )，表示当前棋盘的列数。
Output
对于每次游戏输出一行一个整数，表示铺满当前棋盘的方案总数对 109 + 7 取模后的值。
Sample Input Copy
5
1
3
4
2
6
Sample Output Copy
1
5
11
3
43
HINT
下图为 n = 3 时对应的可能的铺棋子方案。
