9686 - 发愤涂墙(递推)
时间限制 : 1 秒
内存限制 : 128 MB
有一面墙，被垂直的分成了 n 个区域，现在要涂墙，每块墙壁可以涂成红色、蓝色或白色。但是涂墙时必须满足一下条件：
1.两块相邻的墙不能涂成同一种颜色。
2.蓝色的墙必须涂在白墙和红墙中间。
现求所有涂墙的方案数。
输入
输入一个整数 n。（1≤n≤45）
输出
输出方案总数。
样例
输入
3
输出
4