← 返回题目列表

AtCoder · abc122_d

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

示例输出 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.