機巧魔術——那是由內藏魔術迴路的「自動人偶」與「人偶使」所使用的魔術。在某島最高學府的高雄皇家機巧高級中學裡，正舉行著一場選出頂尖人偶使「魔王」的戰鬥「夜會」。

校園內，有一位少年，因為他實在太廢了，歷史上未記載他的名字，就姑且叫他枕頭君吧。枕頭君自從和名為「初音」的少女型自動人偶，在「夜會」上慘烈燒機而以極度難堪的模樣退役後，便整日渾渾噩噩，形同行屍走肉。這天，在製作魔術材料的課程上，他一如往常地耍廢、打瞌睡。隱隱約約，他聽到講台上遠近馳名的趙教授敘述著製造「夏娃的心臟」的特定零件的手續。

「只要將過量的 $C{l}_2$ 分子和長度為 $n$ 的直鏈烷混合，注入魔力，再詠唱咒語『鐘凡喵喵蹦』即可喔。」

但是，這兩種材料每次結合的比例、形狀常常不甚相同，也因此能構造出性質相異的「夏娃的心臟」。例如，當 $n=2$ 時總共有下列 9 種組合方式：

Copy

   H H       H  H       H H        Cl H       H  H        H  H        Cl H        Cl Cl      Cl Cl
   | |       |  |       | |        |  |       |  |        |  |        |  |        |  |       |  |
Cl-C-C-H  Cl-C--C-H  Cl-C-C-Cl  Cl-C--C-H  Cl-C--C-Cl  Cl-C--C-Cl  Cl-C--C-Cl  Cl-C--C-H  Cl-C--C-Cl
   | |       |  |       | |        |  |       |  |        |  |        |  |        |  |       |  |
   H H       Cl H       H H        Cl H       Cl H        Cl Cl       Cl H        Cl Cl      Cl Cl

因為枕頭君太廢了，什麼都不會，請你幫他算出不同的 $n$ 時的組合個數。另外由於答案可能很大，請將輸出的結果 $mod{10}^9+7$。

Input

輸入第一行有一個正整數 $t$（$t\le 100$）表示詢問次數。
接下來的 $t$ 行，每一行有一筆詢問 $n$。

Output

輸出 $t$ 行，每行有一個整數，代表該次詢問的答案 $(mod{10}^9+7)$。

Constraints

第 $1$ 組測資（25%）的 $n\le 10$。

第 $2$ 組測資（25%）的 $n\le 3000$。

第 $3$ 組測資（25%）的 $n\le {10}^6$。

第 $4$ 組測資（25%）的 $n\le {10}^{18}$。

Sample Input

2
1
2

Sample Output

4
9

Hint

機巧少女不會受傷