216. 塗色方法

塗色方法

卦長有$N$顆石頭，他將它們排成一排，發現石頭的顏色就灰灰的不好看，所以卦長想將這些石頭塗成紅、綠、藍三種顏色其中之一。

由於一些奇怪的原因，他希望藍色和綠色不要相鄰，而且頭尾也不能一藍一綠。請問在這個限制下，共有幾種不同的塗色方法呢？

輸入說明

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

每筆測資只包含一個正整數$N$，表示卦長要將$N$個零錢塗色，$1 \leq N \leq 100000$。

輸出說明

對於每筆測資，輸出塗色方法數除以$1000007$的餘數。

範例輸入

4 1 2 3 100000

範例輸出

3 7 15 918955

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

Judge Setting

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