分数: 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
示例输出 1
61
有 4^3 = 64 长度的字符串 3 不包含除 A, C, G 和 T。其中,仅 AGC, ACG 和 GAC 违反了条件,所以答案是 64 - 3 = 61.
示例输入 2
4
示例输出 2
230
示例输入 3
100
示例输出 3
388130742
一定要打印字符串的模数 10^9+7.