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

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

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

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

   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

機巧少女不會受傷