#Z5018. 墙壁涂色

墙壁涂色

阿Q觉得白色的墙面好单调,他决定给房间的墙面涂上颜色。他买了 3 种颜料分别是红、黄、蓝,然后把房间的墙壁竖直地划分成 n 个部分,阿Q希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。

例如,当 n=5 时,下面就是一种合法方案。

5010.jpg

由于墙壁是一个环形,所以下面这个方案就是不合法的。

5011.jpg

输入格式

一个整数 n,表示房间被划分成多少部分。1n50(1 \leq n \leq 50)

输出格式

一个整数,表示给墙壁涂色的合法方案数。

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 painting.in,输出文件为 painting.out

样例输入

4

样例输出

18