不含 AGC 的字符串

题目描述

给定整数 $N$。求满足以下条件、长度为 $N$ 的字符串的个数除以 $10^9+7$ 的余数。

• 不包含 A、C、G、T 以外的字符。
• 不包含 AGC 作为子串。
• 不能通过进行 $1$ 次相邻两个字符的交换来违反上述条件。

输入格式

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

$N$

输出格式

输出满足条件的字符串的个数除以 $10^9+7$ 的余数。

样例

3

61

只包含 A、C、G、T、长度为 $3$ 的字符串共有 $4^3 = 64$ 种，其中只有 AGC、ACG、GAC 违反条件，所以答案是 $64 - 3 = 61$ 种。

4

230

100

388130742

别忘了输出字符串个数除以 $10^9+7$ 的余数。

数据范围

• $3 \le N \le 100$

提示

字符串 $T$ 的子串是指从 $T$ 的开头和末尾去掉 $0$ 个以上字符后得到的字符串。

例如，ATCODER 的子串包含 TCO、AT、CODER、ATCODER、``（空字符串），不包含 AC。