题目描述

$n$ 块砖排成一行，每块砖可以被涂成红、蓝、绿、黄四种颜色，求最后涂为红、绿的砖的数目均为偶数的方案数。结果对 $10007$ 取模。

输入格式

第一行一个整数 $T$，表示下来有 $T$ 组数据。每组数据一个整数 $n$ $(1 \le n \le 10^9)$。

输出格式

每组数据输出一行一个整数，表示方案数模 $10007$。

输入输出样例

输入 #1

2
1
2

输出 #1

2
6