有一个 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。
有一个 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 ）。
输出一个整数，表示铺法总数。
3
3
课课通