派大星每天三點都會醒來吃美味蟹堡，久而久之他就變胖了，珊迪為了讓他減肥，提出了一個計畫。

首先先定義完美二元樹，$T(n)$ 代表深度是 $n$ 的完美二元樹。

$T(1)$ 只有一個節點，這個節點為根節點。

$T(n)$ 為一個根節點各連一條邊到兩個 $T(n-1)$ 的根節點所形成的一棵 $2^n-1$ 個點的有根樹。

$T(n)$ 中，每個節點的編號滿足： (1)根節點的編號是 $1$。 (2)若節點 $i$ 不是葉節點，則其左孩子的編號為 $2i$，右孩子的編號為 $2i+1$。

下圖為 $T(3)$。

如果不懂，請參見 perfect binary tree

我們稱 $T(n)$ 上的一組三元數組 $(i,j,k)$ 是「美味」的，若 $i<k,j\ne i,j\ne k$ 且節點 $i$ 到節點 $k$ 的最短路徑會經過節點 $j$。

定義 $f(n)$ 為 $T(n)$ 上美味的三元數組的數量。

每次吃美味蟹堡前，珊迪會給他一個正整數 $n$，他必須回答出 $f(n)$ 除以 ${10}^9+7$ 的餘數才能吃他的美味蟹堡。

派大星不會數數，所以他偷偷拜託你幫他求出答案，他一共會問你 $t$ 次。

Input

第一行輸入一個正整數 $t$。

$1\le t\le 10000$

接下來輸入 $t$ 行，其中第 $i$ 行輸入一個正整數 $n_i$。

$1\le n_i\le {10}^{18}$

Output

輸出 $t$ 行，其中第 $i$ 行輸出 $f(n_i)(\mathrm{mod}{10}^9+7)$ 的值。

Constraints

第 $1$ 組測資, $n_i\le 10$。$(6\text{\%})$

第 $2$ 組測資, $n_i\le {10}^3$。$(11\text{\%})$

第 $3$ 組測資, $n_i\le {10}^6$。$(17\text{\%})$

第 $4$ 組測資, $n_i\le {10}^9$。$(31\text{\%})$

第 $5$ 組測資, 沒有其他限制。$(35\text{\%})$

Sample Input 1

3
1
2
3

Sample Output 1

0
1
27

Notes

$f(1)=0$ 因為沒有三元數組是美味的

$f(2)=1$ 因為只有$(2,1,3)$是美味的

$T(3)$ 中，$(4,2,5),(2,1,6),(1,2,4)$ 都是美味的，但 $(4,5,6),(2,6,7),(6,1,7)$ 都是不美味的。