AT_ndpc2026_a ポリオミノ

你有无限个以下两种类型的多连块（Polyomino）： - 一个尺寸为 $2$（高）×$1$（宽）的矩形多连块； - 一个 $L$ 形多连块，由 $2 \times 2$ 的正方形去掉一个 $1 \times 1$ 的小方格得到。 现给定一个大小为 $2$（高）×$N$（宽）的网格。你需要用上述多连块完全覆盖网格的所有单元格，条件如下： - 网格的每个单元格必须被恰好一个多连块覆盖； - 多连块在放置时可以任意旋转。 请计算满足条件的放置多连块方法的数量。注意，两种方案即使可通过旋转或翻转整个网格得到对方，也被认为是不同的方案。同时，形状相同的多连块不可区分。

输入从标准输入中给出，格式如下： > $N$

输出有效铺法的总数。

### 样例解释 1 共有 $5$ 种有效的铺法，如下图所示。  ### 数据范围 - $1 \leq N \leq 40$ - $N$ 为整数。 由 ChatGPT 5 翻译