题目描述

从包含A、B、C三个元素的集合中选取元素，生成一个长度为N的字符序列，要求序列中不存在两个位置相邻的不重叠二元子串（长度为2的连续子序列）内容相同，即不能出现形如xyxy的连续四字符模式。

示例：

• N=5时ABCBA是合格序列；
• 序列ABCBC不合格，因为子串BCBC中二元块BC重复出现；
• 序列ABABC不合格，因为子串ABAB中二元块AB重复出现。

输入描述

输入一个整数 N（1 ≤ N ≤ 12）。

输出描述

输出满足规则的序列总个数。

输入样例

4

输出样例

72