分数: 2 点
问题陈述
您拥有无限数量的以下两种类型的多骨牌:
- 大小为矩形的多骨骨牌 2 (高度)× 1 (宽度)
- 通过去除一个而形成的 L 形多骨骨牌 1 \times 1 方形 2 \times 2 广场
给你一个尺寸的网格 2 (高度)× N (宽度)。您希望在以下条件下使用这些多骨牌完全平铺网格的所有单元格:
- 网格的每个单元格必须恰好被一个多联骨牌覆盖。
- 放置多骨牌时您可以旋转它们。
找出满足这些条件的多骨牌的放置方式的数量。请注意,即使可以通过旋转或翻转整个网格从另一种获得一种排列,两种排列也被视为不同。而且,相同形状的多骨牌是无法区分的。
约束
- 1 \leq N \leq 40
- N 是一个整数
输入
输入由标准输入给出,格式如下:
N
输出
打印有效平铺的数量。
示例输入 1
3
示例输出 1
5
有 5 有效的平铺如下所示。

示例输入 2
40
示例输出 2
25366833951139