该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

某校准备举办校庆，现在要在所有教学楼的窗户上布置彩带。彩带是竖条状，所有彩带满足以下两个条件： (1)相同颜色的彩带不能放在相邻的位置； (2)一条蓝色彩带必须放在一条白色的彩带和一条红色的彩带中间。 现在，他想知道满足要求的放置彩带的方案数有多少种。 例如：窗户有n格，n=3时的放置方案有4种，如图：

Format

Input

一行一个整数$n(1\leq n \leq 45)$，表示该窗户的格数

Output

一行一个整数，表示窗户放置彩带的所有可行方案的总数

Samples

3

4

Limitation

1s, 1024KiB for each test case.