AT_abc122_d [ABC122D] We Like AGC

题目描述

给定一个整数 $N$。请计算满足以下条件的长度为 $N$ 的字符串的数量，并输出其对 $10^9+7$ 取模的结果。

• 只包含 A、C、G、T 四种字符。
• 不包含 AGC 作为子串。
• 不能通过交换任意相邻的两个字符一次，使得字符串违反上述条件。

输入格式

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

$N$

输出格式

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

样例 1

输入

3

输出

61

样例 2

输入

4

输出

230

样例 3

输入

100

输出

388130742

说明/提示

注释

字符串 $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 翻译