215. 數磁磚

數磁磚

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

請你幫忙卦長做計算吧

輸入說明

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

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

輸出說明

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

範例輸入

4 1 2 4 100000

範例輸出

0 3 11 232803

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

Judge Setting

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