配点 : $400$ 点

問題文

整数 $N$ が与えられます。次の条件を満たす長さ $N$ の文字列の数を $10^9+7$ で割った余りを求めてください。

• A, C, G, T 以外の文字を含まない。
• AGC を部分文字列として含まない。
• 隣接する $2$ 文字の入れ替えを $1$ 回行うことで上記の条件に違反させることはできない。

注記

文字列 $T$ の部分文字列とは、$T$ の先頭と末尾から $0$ 文字以上を取り去って得られる文字列です。

例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, `` (空文字列) が含まれ、AC は含まれません。

制約

• $3 \leq N \leq 100$

入力

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

$N$

出力

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

3

61

A, C, G, T 以外の文字を含まない長さ $3$ の文字列は $4^3 = 64$ 通り存在し、そのうち AGC, ACG, GAC のみが条件に違反するため、答えは $64 - 3 = 61$ 通りです。

4

230

100

388130742

文字列の数を $10^9+7$ で割った余りを出力することをお忘れなく。