题目描述

用白、蓝、红三种颜色的彩带排成一行，长度为 $n$。相邻两条颜色不能相同；每条蓝色彩带的左右两边必须分别为一条白色和一条红色。因此蓝色不能在行的两端。求不同颜色序列的数量。

输入格式

一行一个整数 $n$。

输出格式

输出方案数。

样例

3

4

数据范围

对于 $30\%$ 的数据，$1\le n\le15$；对于 $100\%$ 的数据，$1\le n\le45$。