We Like AGC

题目描述

你被给定一个整数 $N$。求满足下列条件的长度为 $N$ 的字符串的数量，对 $10^9+7$ 取模：

字符串中只包含 $A$、$C$、$G$ 和 $T$。 字符串中不包含 $AGC$ 作为子串。 通过交换一次相邻的两个字符不能使上述条件被违反。

输入格式

输入按以下格式从标准输入给出： $N$

输出格式

输出满足下列条件的长度为 $N$ 的字符串的数量，对 $10^9+7$ 取模。

3

61

4

230

100

388130742

提示

$3 \leq N \leq 100$字符串 $T$ 的子串是通过从 $T$ 的开头和结尾删除零个或多个字符得到的字符串。 例如，$ATCODER$ 的子串包括 $TCO$、$AT$、$CODER$、$ATCODER$ 和 $$（空字符串），但不包括 $AC$。长度为 $3$ 的不包含除 $A$、$C$、$G$ 和 $T$ 以外字符的字符串共有 $4^3 = 64$ 个。在它们之中，只有 $AGC$、$ACG$ 和 $GAC$ 违背了该条件，所以答案是 $64 - 3 = 61$。
注意要对 $10^9+7$ 取模后输出。

标签: AtCoder|abc122D

来源

AtCoder|abc122D