题目描述

给定一个整数 $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

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

示例输入 2

4

示例输出 2

230

示例输入 3

100

示例输出 3

388130742

请确保打印的字符串数量取模 $10^9+7$。