11107 - 骨牌问题

11107 - 骨牌问题

讨论

统计

通过次数

16

提交次数

36

旧版界面

时间限制 : 1 秒

内存限制 : 64 MB

有一个 $2 \times n$ 的长方形方格，需要用若干 $1 \times 2$ 的骨牌（即覆盖 1 行 2 列或 2 行 1 列的矩形）恰好铺满整个方格。骨牌可以横放或竖放，但不能重叠或超出边界。

请计算铺满 $2 \times n$ 方格的不同铺法总数。

例如， $n=3$ 时，为 $2 \times 3$ 方格，此时用3个 $1 \times 2$ 的骨牌铺满方格，共有3种铺法，见图9.5-5。

输入

输入只有一行，包含一个整数 $n （1 \le n \le 30 ）$ 。

输出

输出一个整数，表示铺法总数。

样例

输入

输出

来源

课课通