2×n 巧克力的切法

题目描述

有一块大小为 $2 \times n$ 的巧克力（长为 $n$、宽为 $2$ 的矩形）。
现在要把它切成若干块大小为 $2 \times 1$ 的小块（可以理解为骨牌），每一小块必须完整保留。
问一共有多少种不同的切割（等价的摆放）方法？

两种方法只要存在某一小块位置不同，就视为不同的方法。

例如：

• 当 $n = 1$ 时，只能竖着放，只有 $1$ 种方法；
• 当 $n = 2$ 时，可以全部竖着放，或者全部横着放，共 $2$ 种方法。

输入格式

输入只有一行，包含一个整数 $n$，表示巧克力的长度。

输出格式

输出一行，一个整数，表示不同切法的数量。

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

2

输出 #2

2

数据范围

对于 $100\%$ 的数据，保证 $1 \le n \le 50$。
结果在 $64$ 位有符号整数范围内。