Description

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

Input Format

一个整数N

Output Format

所有序列和的总数

4

72

Hint

无

Source

搜索与回溯 搜索 字符串 玄级