問題文

やむなく君はお菓子を食べることが大好きです。今日を $1$ 日目として、今日から $N$ 日間、お菓子をどのように食べるかを考えることにしました。そこで、以下のルールを設定しました。

• お菓子は毎日朝、昼、晩の $3$ 回食べる。
• それぞれで食べるお菓子は「クッキー」「チョコレート」「ケーキ」のいずれか $1$ つにする。
• 同じお菓子を $2$ 回連続で食べない。( $i$ 日目の晩と $(i+1)$ 日目の朝についても適用される。)
• 朝に食べるお菓子は「クッキー」「チョコレート」のどちらかにする。

$N$ 日間、合計 $3N$ 回のお菓子について、上のルールをすべて満たすような食べ方の組み合わせが何通りあるかを $10^9+7$ で割った余りを計算してください。

なお、$1$ 日目の朝は「クッキー」「チョコレート」のどちらを食べてもよく、やむなく君は $3$ 種類のお菓子すべてを十分たくさん持っているものとします。

制約

• $1\le N\le 10^{18}$
• $N$ は整数

部分点

この問題には部分点が設定されています。

• $N \leq 10^5$ を満たす入力に正解すると、$300$ 点が与えられます。

入力例 1Copy

1

出力例 1Copy

8

クッキーを「ク」、ケーキを「ケ」、チョコレートを「チ」と表すと、

(朝、昼、晩) $=$ (ク、ケ、ク), (ク、ケ、チ), (ク、チ、ク), (ク、チ、ケ), (チ、ケ、ク), (チ、ケ、チ), (チ、ク、ケ), (チ、ク、チ)

の $8$ 通りです。同じお菓子が連続してはいけないこと、朝にはケーキを食べないことに注意してください。

入力例 2Copy

2

出力例 2Copy

40

入力例 3Copy

100000

出力例 3Copy

607318103