問題文

A,B,Cの $3$ つのバス停があります。

時刻 $0$ にバス停Aにバスが $1$ 台止まっていて、バス停A以外にはバスがいません。

時刻 $i=0,1,2,...,N-1$ に各バス停にいるバスはそれぞれ以下のように動きます。

• バス停Aにバスがいる場合

• 確率 $\frac{1}{3}$ でバス停Bに時間 $1.5$ かけて移動する

• 確率 $\frac{1}{3}$ でバス停Cに 時間 $1.5$ かけて移動する

• 確率 $\frac{1}{3}$ でバス停Aにとどまる

• バス停Bにバスがいる場合

• 確率 $\frac{1}{3}$ でバス停Cに時間 $1.5$ かけて移動する

• 確率 $\frac{1}{3}$ でバス停Aに時間 $1.5$ かけて移動する

• 確率 $\frac{1}{3}$ でバス停Bにとどまる

• バス停Cにバスがいる場合

• 確率 $\frac{1}{3}$ でバス停Aに時間 $1.5$ かけて移動する

• 確率 $\frac{1}{3}$ でバス停Bに時間 $1.5$ かけて移動する

• 確率 $\frac{1}{3}$ でバス停Cにとどまる

時刻 $N$ にバス停Aにバスが1台以上いる確率を $\mod 10^9+7$ で出力してください。

$T$ 個のテストケースに答えてください。

入力

$T$

1行目にはテストケースの数 $T$ が与えられる。

各テストケースは以下のようになっており、$T$ 行与えられる。

$N$

整数 $N$ が与えられる。

制約

• $1≤T≤3\times10^3$

• $1≤N≤1\times10^9$

• 入力は全て整数である

サンプル

5
3
5
10
100
1000000000

370370373
930041159
79120731
511323553
802083332