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

首先先定義完美二元樹，\(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\neq i,j\neq 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)\pmod{10^9+7}\) 的值。

Constraints

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

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

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

第 \(4\) 組測資, \(n_i\le10^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)\) 都是不美味的。