Description

从三个元素的集合 A,B,C中选取元素生成一个N个字符组成的序列，使得没有两个相邻字的子序列（子序列长度=2）相同。
例： N=5时 ABCBA 是合格的，而序列 ABCBC 与 ABABC 是不合格的，因为其中子序列 BC，AB 是相同的。
对于由键盘输入的 N，求出满足条件的 N 个字符的总数。

Sample 1

Input

4

Output

72

Limitation

1s, 256MiB for each test case.
1≤N≤12