AT_ndpc2026_a.Polyomino

You have an unlimited number of the following two types of polyominoes:

• A rectangular polyomino of size $2$ (height) × $1$ (width)
• An L-shaped polyomino formed by removing one $1 \times 1$ square from a $2 \times 2$ square

You are given a grid of size $2$ (height) × $N$ (width). You want to completely tile all cells of the grid using these polyominoes under the following conditions:

• Each cell of the grid must be covered by exactly one polyomino.
• You may rotate the polyominoes when placing them.

Find the number of ways to place the polyominoes satisfying these conditions. Note that two arrangements are considered different even if one can be obtained from the other by rotating or flipping the entire grid. Also, polyominoes of the same shape are indistinguishable.

你有无限多个以下两种类型的多格骨牌：

• 一个大小为 $2$（高）× $1$（宽）的矩形多格骨牌；
• 一个 L 形多格骨牌，由从一个 $2 \times 2$ 正方形中移除一个 $1 \times 1$ 小方格得到。

给定一个大小为 $2$（高）× $N$（宽）的网格。你需要用上述多格骨牌完全铺满该网格的所有格子，并满足以下条件：

• 网格中的每个格子必须恰好被一个多格骨牌覆盖；
• 放置多格骨牌时可以对其进行旋转。

求满足上述条件的放置方案数。注意：即使一种方案可通过旋转或翻转整个网格得到另一种方案，这两种方案仍被视为不同。此外，形状相同的多格骨牌彼此不可区分。

The input is given from standard input in the following format:

$N$

输入从标准输入中按以下格式给出：

$N$

Print the number of valid tilings.

输出有效铺砖方案的数量。

Sample 1 Explanation:
There are $5$ valid tilings as shown below.

Constraints

• $1 \leq N \leq 40$
• $N$ is an integer

样例 1 解释：
如下图所示，共有 $5$ 种有效的铺法。

约束条件

• $1 \leq N \leq 40$
• $N$ 是一个整数