题目描述

从三个元素的集合 [A，B，C] 中选取元素生成一个 N 个字符组成的序列,使得没有两个相邻的子序列相同（子序列长度固定为 2 ）。例：N=5 时 ABCBA 是合格的，而序列 ABCBC 与 ABABC 是不合格的，因为其中子序列 BC，AB 是相同的。

输入格式

一个整数 n ( 1 ≤ n ≤ 15 )。

输出格式

满足条件的 N 个字符的序列总数。

样例

4

72