有一个 $4\times n$ 的拼图空槽，试问用 $4\times 1$ 和 $2\times 2$ 的拼图完全填充该拼图槽的方案数。
答案对 $10^9+7$ 取模。
有一个 $4\times n$ 的拼图空槽，试问用 $4\times 1$ 和 $2\times 2$ 的拼图完全填充该拼图槽的方案数。
答案对 $10^9+7$ 取模。
第一行一个整数 $T$ $($ $T\leq 50000$ $)$，表示该组数据包含的测试用例数。
接下来 $T$ 行，一行一个整数 $n$ $($ $n\leq 10^{18}$ $)$，表示该测试用例。
输出 $n$ 行一行一个整数，表示你的答案对 $10^9+7$ 取模的结果。
输入
4 1 2 3 4
输出
1 2 3 9