D - 我们喜欢AGC

得分：400 分

问题描述

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

• 字符串中除了 A、C、G 和 T 之外没有其他字符。
• 字符串中没有子串 AGC。
• 进行一次邻字符交换后，不会违反以上条件。

注意事项

字符串 $T$ 的子串是通过从 $T$ 的开头和末尾移除零个或多个字符得到的字符串。

例如，ATCODER 的子串包括 TCO、AT、CODER、ATCODER 和空字符串，但不包括 AC。

约束条件

• $3 \leq N \leq 100$

输入

从标准输入提取数据，格式如下：

N

输出

打印满足以上条件的长度为 $N$ 的字符串的数量，对 $10^9+7$ 取模。

样例解释

样例 1

对于长度为 3 的字符串，除了 AGC、ACG 和 GAC 之外，有 $4^3 = 64$ 种不包含其他字符的选择，因此答案是 $64 - 3 = 61$。

样例 2

对于长度为 4 的字符串，有 $4^4 = 256$ 种不包含其他字符的选择，其中只有 AGC 这一个子串违反了条件，因此答案是 $256 - 1 = 255$。

样例 3

长度为 100 的字符串共有 $4^{100}$ 种不包含其他字符的选择，并且可以使用大数运算求出，但为了避免数值过大，最后的结果是 $388130742$。