高塔计数

题目描述

Y 同学正在玩一种积木游戏。他拥有无限多个长和宽均为正整数的矩形积木。

现在，Y 同学希望使用这些积木在一个平面上搭建一个宽度为 $2$、高度为 $N$ 的塔（即填满一个 $2 \times N$ 的网格区域）。搭建规则如下：

1. 积木之间不能重叠。
2. 积木必须恰好铺满整个 $2 \times N$ 的区域，不能有空隙，也不能超出边界。
3. 积木的边缘必须与网格线对齐。

Y 同学想知道，一共有多少种不同的搭建方案？ 两个方案被认为是不同的，当且仅当存在某个网格边界，在一种方案中是积木的边缘，而在另一种方案中是积木的内部（或者反之）。

由于方案数可能非常大，请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。 接下来 $T$ 行，每行包含一个正整数 $N$，表示塔的高度。

输出格式

对于每组测试数据，输出一行一个整数，表示搭建方案数对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

2
1
2

样例输出 #1

2
8

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 100$，$1 \le N \le 10^6$。