Description

由字符‘A’,’B’,‘C’组成一个长度为l的字符串，要求没有两个相邻的子串相同，请问有多少种组法。如N =5时ABCBA是合格的，而序列ABCBC与ABABC是不合格的，因为其中子串BC，AB是相同的

Input Format

输入仅有一个整数l。

Output Format

输出满足条件的字符串的种数。

3

12

Hint

【样例1说明】

12种字符串分别是：ABA ABC ACA ACB BAB BAC BCA BCB CAB CAC CBA CBC

【数据范围】

100%数据：1<=l<=15