AT_abc122_d [ABC122D] We Like AGC

给定一个整数 $N$。请计算满足以下条件的长度为 $N$ 的字符串的数量，并输出其对 $10^9+7$ 取模的结果。 - 只包含 `A`、`C`、`G`、`T` 四种字符。 - 不包含 `AGC` 作为子串。 - 不能通过交换任意相邻的两个字符一次，使得字符串违反上述条件。

输入为以下格式，通过标准输入给出。 > $N$

请输出满足条件的字符串数量对 $10^9+7$ 取模的结果。

### 注释 字符串 $T$ 的子串是指通过从 $T$ 的开头和结尾各去掉 $0$ 个或多个字符后得到的字符串。 例如，`ATCODER` 的子串包括 `TCO`、`AT`、`CODER`、`ATCODER`、``（空字符串），但不包括 `AC`。 ### 约束 - $3 \leq N \leq 100$ ### 样例解释 1 只包含 `A`、`C`、`G`、`T` 的长度为 $3$ 的字符串共有 $4^3 = 64$ 种，其中只有 `AGC`、`ACG`、`GAC` 不满足条件，因此答案为 $64 - 3 = 61$ 种。 ### 样例解释 3 请不要忘记输出字符串数量对 $10^9+7$ 取模的结果。 由 ChatGPT 4.1 翻译