问题描述

具体描述见教材p242： 一个只包含A、B、C三种字符的字符串，如果其中有连续的3个由A、B、C各一个组成的子串，则称这个字符串为string字符串。 例如： BAACAACCBAAA就是一个 string字符串，而 AABBCCAABB则不是。 你的任务是计算只包含A、B、C三种字符且长度为n的这种字符串有多少个不是string字符串。

格式

输入

1个整数n(1≤n≤30)。

输出

1个整数。

样例

2

9

3

21

限制

1s, 64MB.