AT_ndpc2026_a ポリオミノ

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.

The input is given from standard input in the following format: > $ N $

Print the number of valid tilings.

### Sample Explanation 1 There are $ 5 $ valid tilings as shown below.  ### Constraints - $ 1 \leq N \leq 40 $ - $ N $ is an integer