题目描述

您将得到一个整数 $N$，请找出满足下列要求的长度为 $N$ 的字符串的数目，答案对 $10^9+7$ 取模。

• 该字符串仅由 ACGT 四种字符组成。
• 该字符串不包含子串 AGC。
• 交换相邻两个字符一次不违反上述要求。

输入格式

一个正整数 $N\ (3 \le N \le 100)$。

输出格式

满足题目要求的字符串个数。

3

61

4

230

100

388130742