给定正整数 $n$，共有 $2^n$ 个顶点，编号为 $0, 1, 2, \ldots, 2^n-1$。对每个顶点 $x$，执行如下操作：

1. 将 $x$ 表示为无前导零的二进制字符串；
2. 将该二进制字符串整体翻转。可以证明，翻转后的字符串仍然是一个合法的二进制表示（但可能包含前导零）。记该二进制表示对应的数值为 $y$。

在顶点 $x$ 与顶点 $y$ 之间连一条无向边。

例如：$6=(110)_2$，翻转后得到二进制串 $011$，其对应的数值为 $3$，因此在顶点 $6$ 与顶点 $3$ 之间连边。

记 $dis(x, y)$ 为顶点 $x$ 到顶点 $y$ 的最短路长度。若 $x$ 与 $y$ 不连通，则规定 $dis(x, y) = 0$。特别地，规定 $dis(x, x) = 0$。

求： $$ S = \sum_{x=0}^{2^n-1} \sum_{y=0}^{2^n-1} dis(x, y) $$

由于答案可能很大，请输出 $S$ 对 $10^9 + 7$ 取模后的值。

Input

本题有多组测试数据。对于每组测试数据：

第一行一个正整数 $t$ ($1 \le t \le 5 \times 10^5$)，表示数据组数。

接下来 $t$ 行，每行一个正整数 $n$ ($1 \le n \le 10^9$)。

Output

对于每组数据，输出一行一个整数表示答案。

Examples

Input 1

5
1
2
3
10
100

Output 1

0
2
10
7732
776991294

Note

当 $n=2$ 时，有 $4$ 个点，编号为 $0,1,2,3$，其中 $0$ 向 $0$ 连边，$1$ 向 $1$ 连边，$2$ 向 $1$ 连边，$3$ 向 $3$ 连边。其中：

$$dis(0,0)=0,dis(0,1)=0,dis(0,2)=0,dis(0,3)=0$$

$$dis(1,0)=0,dis(1,1)=0,dis(1,2)=1,dis(1,3)=0$$

$$dis(2,0)=0,dis(2,1)=1,dis(2,2)=0,dis(2,3)=0$$

$$dis(3,0)=0,dis(3,1)=0,dis(3,2)=0,dis(3,3)=0$$

故总和为 $2$。