夏娃的心臟

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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

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

「只要將過量的 \(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

機巧少女不會受傷


Comments

There are no comments at the moment.