题目描述

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

• 高为 $2$ 格、宽为 $1$ 格的长方形骨牌；
• 从一个 $2\times 2$ 的正方形中去掉一个 $1\times 1$ 方格后得到的 L 形骨牌。

现有一个高为 $2$ 格、宽为 $N$ 格的网格。你需要使用这些骨牌将网格完全铺满，并满足：

• 网格中的每个方格恰好被一块骨牌覆盖；
• 放置骨牌时可以旋转骨牌。

求满足条件的铺法数量。

将整个网格旋转或翻转后才能重合的两种铺法仍视为不同铺法。同一种形状的骨牌之间不作区分。

限制条件

• $1\le N\le 40$
• $N$ 为整数。

输入

输入通过标准输入按以下格式给出：

N

输出

输出满足条件的铺法数量。

样例输入 1

3

样例输出 1

5

满足条件的铺法共有 $5$ 种。

样例输入 2

40

样例输出 2

25366833951139