Migrated from Lutece 1295 一道简单题~~

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

我们有一个大小为2 × 2 × n的长方体，考虑其中每一个1 × 1 × 1块作为点，如果两个块有通过一个面直接接触我们认为这两个点有边相连，问在这个图中有多少条互不相同的哈密顿回路？哈密顿回路就是一个访问了所有节点的环。

Input

第一行有一个数字 T(T ≤ 100) 代表数据组数。 接下去有T行，每行一个数代表询问 n(1 ≤ n ≤ 1000000000).

Output

每组数据输出一行代表答案，记得取模1000000007~~~~

Samples

4
1
2
3
10

Case 1: 1
Case 2: 6
Case 3: 22
Case 4: 221542