题目描述

熊猫接到了一项给一排方块涂色的任务。由于熊猫是个聪明的孩子，他开始思考一个关于涂色的数学问题。假设一排有 $N$ 个方块，每个方块可以涂成红色、蓝色、绿色或黄色。出于某种神秘的原因，熊猫希望红色方块和绿色方块的数量均为偶数。在此条件下，熊猫想知道有多少种不同的涂色方式。 输入格式

第一行包含一个整数 $T（1≤T≤100）$，表示测试用例的数量。 接下来 $T$ 行，每行包含一个整数 $N（1≤N≤10⁹）$，表示方块的数量。

输出格式

对于每个测试用例，输出一行表示涂色方式的数量。由于答案可能很大，请对 $10007$ 取模。

输入样例 1

plaintext 2
1
2

输出样例 1

plaintext 2
6