P15220 [SWERC 2017] Macarons

Pierre 以制作马卡龙而闻名。他制作圆形的马卡龙，存放在尺寸为 $1 \times 1$ 的方形盒子中；以及椭圆形的马卡龙，存放在尺寸为 $1 \times 2$（或者旋转后，尺寸为 $2 \times 1$）的矩形盒子中。为了布置自助餐，Pierre 希望用这两种马卡龙铺满一张尺寸为 $N \times M$ 的矩形桌子，这意味着桌子必须完全被覆盖，不留任何空隙。桌子的宽度 $N$ 较小，以便客人能够轻松拿取马卡龙；桌子的长度 $M$ 较大，以容纳大量客人。为了保持桌子的美观，马卡龙的朝向必须始终与桌子的边对齐。 Pierre 想知道有多少种铺满桌子的方式。你能帮助他吗？

输入包含以下整数： - 第一行：整数 $N$； - 第二行：整数 $M$。

输出应包含一行，内容为铺满方式的总数，对 $10^9$ 取模的结果。

### 数据范围 输入满足 $1 \leq N \leq 8$ 且 $1 \leq M \leq 10^{18}$。 翻译由 DeepSeek 完成