测试数据来自 oistream/1138

背景

• Idea: 8bits 出题组
• Data: 8bits 出题组
• Std: 8bits 出题组
• 题面: 8bits 出题组

本题版权归 7FOJ 合作伙伴 8bits 出题组 所有。

描述

小 LuV 兴致勃勃地玩起了骨牌，他决定考考 LuV_Studio 。

现有 \(2\times n\) 的长方形方格，用 \(n\) 个 \(1\times 2\) 的骨牌铺满方格，请你求出铺法总数。

输入格式

一行，\(n\) 表示骨牌个数，及长方形的长。

输出格式

一行，表示铺法总数。

样例

输入样例1

2

输出样例1

2

输入样例2

7

输出样例2

21

数据规模与约定

对于全部数据，\(1\leq n\leq 50\)， 时间限制 \(500~\text{s}\)，空间限制 \(3~\text{MB}\) 。

说明与提示

小LuV:横排列，竖排列……