题目描述

宋城书院 $100$ 周年校庆，小明准备用一些白色、蓝色和红色的彩带来装饰学校超市的橱窗，他希望满足以下两个条件：

(1) 相同颜色的彩带不能放在相邻的位置； (2) 一条蓝色的彩带必须放在一条白色的彩带和一条红色的彩带中间。

现在，他想知道满足要求的放置彩带的方案数有多少种。例如，如下所示为橱窗宽度 $n = 3$ 的所有放置方案，共 $4$ 种。

• 白 - 红 - 白
• 红 - 蓝 - 白
• 白 - 蓝 - 红
• 红 - 白 - 红

输入格式

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

输出格式

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

样例

输入样例

3

输出样例

4

数据范围与提示

对于 $30$ 的数据满足 $1 \le n \le 15$。 对于 $100$ 的数据满足 $1 \le n \le 45$。