题目描述

You are given an integer $N$. Find the number of strings of length $N$ that satisfy the following conditions, mod $10^9+7$:

• The string does not contain characters other than A, C, G and T.
• The string does not contain AGC as a substring.
• The condition above cannot be violated by swapping two adjacent characters once.

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

• 字符串不包含除 A、C、G 和 T 以外的字符。
• 字符串不包含子串 AGC。
• 将两个相邻字符对调一次不会违反上述条件。

输入格式

输入内容按以下格式标准输入：

$N$

输出格式

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

样例 #1

样例输入 #1

3

样例输出 #1

61

样例 #2

样例输入 #2

4

样例输出 #2

230

样例 #3

样例输入 #3

100

样例输出 #3

388130742

说明

字符串 $T$ 的子串是指从 $T$ 的开头和结尾移除 0 个或多个字符后得到的字符串。

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

数据规模与约定

• $3 \leq N \leq 100$

样例 $1$ 解释

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

样例 $3$ 解释

请务必打印取模为 $10^9+7$ 的字符串数。