問題文

やむなく君はお菓子を食べることが大好きです。今日を 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 点が与えられます。

入力例 1

1

出力例 1

8

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

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

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

入力例 2

2

出力例 2

40

入力例 3

100000

出力例 3

607318103