J19 例题-6 Null老师染砖

题目描述

衣食无忧的 $\text{Null}$ 老师 有一天突发奇想，想要去感受一下劳动人民的艰苦生活。

具体工作是这样的，有 $N$ 块砖排成一排染色，每一块砖需要涂上红、蓝、绿、黄这 $4$ 种颜色中的其中 $1$ 种。且当这 $N$ 块砖中红色和绿色的块数均为偶数时，染色效果最佳。

为了使工作效率更高，$\text{Null}$ 老师 想要知道一共有多少种方案可以使染色效果最佳，你能帮帮他吗？

输入格式

第一行为 $T$，代表数据组数。

接下来 $T$ 行每行包括一个数字 $N$，代表有 $N$ 块砖。

输出格式

输出满足条件的方案数，答案模 $10007$。

样例输入1

2
1
2

样例输出1

2
6

样例分析

如上所述。

数据范围

$100\%$ 的数据：$1 \le T \le 100$ , $1 \le N \le 1e9$。