【问题描述】

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

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

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

现在，他想知道满足要求的放置彩带的方案数有多少种。

例如，如图9．4—1所示为橱窗宽度n=3的所有放置方案，共4种。

【程序名】flag

【输入格式】

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

【输出格式】

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

【样例输入】flag.in

3

【样例输出】flag.out

4

【数据规模】

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

对100％的数据满足：1≤n≤45。