题目描述

给定一个整数 $N$。找到满足以下条件的长度为 $N$ 的字符串的数量，对 $10^9+7$取模:

字符串中除了 A、C、G 和T之外没有其他字符。

字符串中没有子串 AGC。

进行一次邻字符交换后，不会违反以上条件。

注意事项

字符串 $T$ 的子串是通过从 $T$ 的开头和末尾移除零个或多个字符得到的字符串,

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

输入

输入一个整数$N$

输出

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

3

61

样例解释

对于长度为3的字符串，除了 AGC、ACG 和 GAC 之外，有 $4^3$= 64种不包含其他字符的选择因此答案是 64 -3 = 61。

4

255

样例解释

对于长度为 4 的字符串，有 $4^4$ = 256 种不包含其他字符的选择，其中只有 AGC 这一个子串违反了条件，因此答案是 256 -1-255。

100

388130742

样例解释

长度为 100 的字符串共有 $4^{100}$ 种不包含其他字符的选择，并且可以使用大数运算求出，但为了避免数值过大，最后的结果是 388130742。

提示

$3 \leq N \leq 100$