题目描述

给定一个数 \(n\)，生成一个\(2^n×2^n\)的 全\(0\) 矩阵。

对于这个矩阵，每次我们把他等分成 \(4\) 分

例：

\(1\)	\(2\)	\(3\)	\(4\)
0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0

变为

\(1\)	\(2\)	\(3\)	\(4\)
0	0	0	0
0	0	0	0
0	0	1	1
0	0	1	1

对于右下角的矩阵，我们把它全置为\(1，\)其余的矩阵再按照上述步骤分，直到分不了为止；

求出矩阵中\(1\)的个数，由于答案很大，我们要求将答案 \(mod10^9+7\)。

格式

输入格式

第一行一个数\(t,\)表示数据组数；

接下来\(t\)行，每行一个数\(n\)，含义如题目所述。

输出格式

共\(t\)行。

每行一个数\(ans,\)含义如题目所述。

样例1

样例输入1

2
1
2

样例输出1

1
7

样例解释

00
01

共 \(1\) 个。

0000
0101
0011
0111

共 \(7\) 个。

限制

对于\(10\%\)的数据，输出即样例；

对于\(30\%\)的数据，\(t<=10,n<=12\)

对于\(60\%\)的数据，\(t<=10^3,(n_1+n_2+...+n_t)<=10^7\)

对于\(100\%\)的数据，\(1<=t<=10^6,0<=n<=10^7\)