题目描述

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

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

输入格式

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

$N$

输出格式

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

题目大意

您将得到一个整数 $N$ ，请找出满足下列要求的长度为 $N$ 的字符串的数目，答案对 $10^9+7$ 取模

• 该字符串仅由 A C G T 四种字符组成
• 该字符串不包含子串 AGC
• 交换相邻两个字符一次不违反上述要求

3

61

4

230

100

388130742

提示

注記

文字列 $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$ で割った余りを出力することをお忘れなく。