问题描述

从 $3$ 个元素的集合 $[A，B，C]$ 中选取元素生成一个 $N$ 个字符组成的序列，使得没有两个相邻的长度为 $2$ 的子串相同。

例： $N=5$ 时 $ABCBA$ 是合格的，而序列 $ABCBC$ 与 $ABABC$ 是不合格的，因为其中子串 $BC$ ， $AB$ 是相同的。

对于由键盘输入的 $N(1<=N<=12)$ ，求出满足条件的 $N$ 个字符的所有序列总数。