题目描述

某中学90周年校庆，小林准备用一些白色、蓝色和红色的彩带来装饰学校超市的橱窗，他希望满足以下两个条件：

(1) 相同颜色的彩带不能放在相邻的位置；

(2) 一条蓝色的彩带必须放在一条白色的彩带和一条红色的彩带中间。

输入格式

一行一个整数 n，表示橱窗宽度(或者说彩带数目)。

输出格式

一行一个整数，表示装饰橱窗的彩带放置方案数

样例数据

input

3

output

4

数据规模与约定

对 30% 的数据满足：1≤n≤15。

对 100% 的数据满足：1≤n≤60。

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$