题目描述

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

输入格式

输入仅有一个整数$\red{n}$($\red{1<=n<=15}$)。

输出格式

输出满足条件的$\red{ N}$个字符的序列总数。

样例

输入样例

4

输出样例

72