AT_ndpc2026_a ポリオミノ

あなたは次の $ 2 $ 種類のポリオミノを無数に持っています： - 縦 $ 2 $ マス、横 $ 1 $ マスの長方形型のポリオミノ - 一辺が $ 2 $ マスの正方形型のポリオミノから一辺が $ 1 $ マスの正方形を $ 1 $ 個取り除いてできる、L 字型のポリオミノ 縦 $ 2 $ マス、横 $ N $ マスのグリッドがあります。あなたは次の条件を満たすようにグリッドの全てのマスにポリオミノを敷き詰めることにしました。 - グリッドの各マスにはちょうど $ 1 $ 個のポリオミノが置かれている。 - ポリオミノを置くときに回転させることができる。 条件を満たすポリオミノの配置の個数を求めてください。ただし、グリッドを回転・反転してはじめて一致する配置は別々に数えます。また、同じ形のポリオミノ同士は区別できないものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $

条件を満たすポリオミノの配置の個数を出力せよ。

### Sample Explanation 1 条件を満たすポリオミノの配置は次の $ 5 $ 通りです。  ### Constraints - $ 1 \leq N \leq 40 $ - $ N $ は整数