AT_cpsco2019_s1_d Dessert Planning

[problemUrl]: https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_d やむなく君はお菓子を食べることが大好きです。今日を $ 1 $ 日目として、今日から $ N $ 日間、お菓子をどのように食べるかを考えることにしました。そこで、以下のルールを設定しました。 - お菓子は毎日朝、昼、晩の $ 3 $ 回食べる。 - それぞれで食べるお菓子は「クッキー」「チョコレート」「ケーキ」のいずれか $ 1 $ つにする。 - 同じお菓子を $ 2 $ 回連続で食べない。( $ i $ 日目の晩と $ (i+1) $ 日目の朝についても適用される。) - 朝に食べるお菓子は「クッキー」「チョコレート」のどちらかにする。 $ N $ 日間、合計 $ 3N $ 回のお菓子について、上のルールをすべて満たすような食べ方の組み合わせが何通りあるかを $ 10^9+7 $ で割った余りを計算してください。 なお、$ 1 $ 日目の朝は「クッキー」「チョコレート」のどちらを食べてもよく、やむなく君は $ 3 $ 種類のお菓子すべてを十分たくさん持っているものとします。

入力は以下の形式で標準入力から与えられます。 > $ N $

答えを $ 1 $ 行に出力してください。

### 制約 - $ 1\le\ N\le\ 10^{18} $ - $ N $ は整数 ### 部分点 この問題には部分点が設定されています。 - $ N\ \leq\ 10^5 $ を満たす入力に正解すると、$ 300 $ 点が与えられます。 ### Sample Explanation 1 クッキーを「ク」、ケーキを「ケ」、チョコレートを「チ」と表すと、 (朝、昼、晩) $ = $ (ク、ケ、ク), (ク、ケ、チ), (ク、チ、ク), (ク、チ、ケ), (チ、ケ、ク), (チ、ケ、チ), (チ、ク、ケ), (チ、ク、チ) の $ 8 $ 通りです。同じお菓子が連続してはいけないこと、朝にはケーキを食べないことに注意してください。