UOJ Logo LFYZ Online Judge

LFYZOJ

#95. 字符序列

统计

问题描述

从三个元素的集合 $[A,B,C]$ 中选取元素生成一个 $N$ 个字符组成的序列,使得没有两个相邻字的子序列(子序列长度=2)相同。例:$N = 5$时 ABCBA 是合格的,而序列 ABCBCABABC 是不合格的,因为其中子序列BCAB是相同的。

对于由键盘输入的 $N(1 \leq N \leq 12)$,求出满足条件的 $N$ 个字符的所有序列和其总数。

输入格式

一行,一个整数 $N$。

输出格式

一个整数,即满足条件的序列总数。

样例一

input

4

output

72

数据范围与约定

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$