215. 數磁磚

0 Judge

Code: 0


數磁磚

有一天,卦長走在鋪滿正方形磁磚的走廊上,腦帶開始活動起來:「如果這條走廊的寬度只有$3$塊磁磚寬,那麼用$1 \times 2 $的長方型磁磚鋪滿這整條走廊一共有幾種方法呢?」

請你幫忙卦長做計算吧

輸入說明

第一行為一個正整數$T$,$T \leq 100000$,表示共有$T$筆測資。

每筆測資只包含一個正整數$N$,表示走廊的長度為$N$個磁磚,$1 \leq N \leq 100000$。

輸出說明

對於每筆測資,輸出不同排列的方法數除以$1000007$的餘數。

範例輸入

範例輸出

以下為$N = 2$的$3$種塗色方法

sprout

Judge Setting

run-time limit: 80 ms
memory limit: 131072 byte
測資數量: 0