AT_abc122_d [ABC122D] We Like AGC

[problemUrl]: https://atcoder.jp/contests/abc122/tasks/abc122_d 整数 $ N $ が与えられます。次の条件を満たす長さ $ N $ の文字列の数を $ 10^9+7 $ で割った余りを求めてください。 - `A`, `C`, `G`, `T` 以外の文字を含まない。 - `AGC` を部分文字列として含まない。 - 隣接する $ 2 $ 文字の入れ替えを $ 1 $ 回行うことで上記の条件に違反させることはできない。

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

条件を満たす文字列の数を $ 10^9+7 $ で割った余りを出力せよ。

### 注記 文字列 $ T $ の部分文字列とは、$ T $ の先頭と末尾から $ 0 $ 文字以上を取り去って得られる文字列です。 例えば、`ATCODER` の部分文字列には `TCO`, `AT`, `CODER`, `ATCODER`, `` (空文字列) が含まれ、`AC` は含まれません。 ### 制約 - $ 3\ \leq\ N\ \leq\ 100 $ ### Sample Explanation 1 `A`, `C`, `G`, `T` 以外の文字を含まない長さ $ 3 $ の文字列は $ 4^3\ =\ 64 $ 通り存在し、そのうち `AGC`, `ACG`, `GAC` のみが条件に違反するため、答えは $ 64\ -\ 3\ =\ 61 $ 通りです。 ### Sample Explanation 3 文字列の数を $ 10^9+7 $ で割った余りを出力することをお忘れなく。