#4042. [GXOI/GZOI2019] 逼死强迫症

[GXOI/GZOI2019] 逼死强迫症

[GXOI/GZOI2019] 逼死强迫症

题目描述

ITX351 要铺一条 2×N2 \times N 的路,为此他购买了 NN2×12 \times 1 的方砖。可是其中一块砖在运送的过程中从中间裂开了,变成了两块 1×11 \times 1 的砖块! ITX351 由此产生了一个邪恶的想法:他想要在这条路上故意把两块 1×11 \times 1 的砖块分开铺,不让两块砖有相邻的边,其他砖块可以随意铺,直到整条路铺满。这样一定可以逼死自身强迫症 sea5!

也许下面的剧情你已经猜到了——他为此兴奋不已,以至于无法敲键盘。于是,他请你帮忙计算一下,有多少种方案可以让自己的阴谋得逞。

输入格式

每个测试点包含多组数据,输入文件的第一行是一个正整数 TT,表示数据的组数。注意各组数据之间是独立无关的。

接下来 TT 行,每行包含一个正整数 NN,代表一组数据中路的长度。

输出格式

输出应包含 TT 行,对于每组数据,输出一个正整数,表示满足条件的方案数。

由于答案可能非常的大,你只需要输出答案对 1000000007(109+7)1000000007 (10^9 + 7) 取模后的结果。

样例 #1

样例输入 #1

3
1
2
4

样例输出 #1

0
0
6

提示

样例中 N=4 N=4 解释见下图:

数据范围

测试点编号 NN 的规模 TT 的规模
11 N10N \le 10 T10T \le 10
22
33 N105N \le 10^5 T50T \le 50
44
55
66 N2×109N \le 2 \times 10^9
77
88
99 T500T \le 500
1010