问题描述

具体描述见教材p172： 从三个元素的集合[A,B,C]中选取元素生成一个N个字符组成的序列，使得没有两个相邻的子序列相同。例如：N=5时ABCBA是合格的，而序列ABCBC和ABABC是不合格的，因为其中子序列BC,AB是相同的。

格式

输入

一个数n(1<=n<=15)

输出

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

样例

3

12

限制

1s, 64MB.