#E. 墙壁涂色

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

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

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

输入格式

一个整数 n，表示房间被划分成多少部分。 $（1 \leq n \leq 50）$

输出格式

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

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

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

样例输入

样例输出

3月9日周六8:10