U362853 [POJ - 3734] Blocks

随机数据。

衣食无忧的 Q老师 有一天突发奇想，想要去感受一下劳动人民的艰苦生活。 具体工作是这样的，有 $N$ 块砖排成一排染色，每一块砖需要涂上红、蓝、绿、黄这 $4$ 种颜色中的其中 $1$ 种。且当这 $N$ 块砖中红色和绿色的块数均为偶数时，染色效果最佳。 为了使工作效率更高，Q老师 想要知道一共有多少种方案可以使染色效果最佳，你能帮帮他吗？

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

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

$1 \le T \le 100$，$1 \le N \le 10^9$.