综合练习

B. 骨牌问题

有一个 $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 ）$ 。

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

时间限制	1 秒
内存限制	64 MB