题目描述

桂林为了欢迎广大游客，决定在桂林的各大街道上布置迎宾彩带。目前有白色、蓝色和红色的彩带，并满足以下两个条件：

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

例如，当街道宽度 $n=3$ 时，共有 $4$ 种放置方案。

输入格式

一行一个整数 $n$，表示彩带数目。

输出格式

一行一个整数，表示彩带放置方案数。输出保证不超过 $10^9$。

样例

输入

3

输出

4

数据范围与提示

$2 \leq n \leq 1000$