Score : $600$ points

问题陈述

我们有一个长 $H$ 米、宽 $W$ 米的矩形房间。
我们将使用长 $2$ 米、宽 $1$ 米的矩形榻榻米，以及边长为 $1$ 米的正方形半畳（hanjo）来铺满整个房间。每个榻榻米可以垂直或水平放置。
请问有多少种不同的方式来铺满这个房间？
请注意，仅经过旋转或镜像后匹配的方式视为相同。

由于计算结果可能非常巨大，请在模 $998244353$ 的情况下找到答案。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a rectangular room that is $H$ meters long and $W$ meters wide.
We will fill this entire room with tatami (rectangular mats) that are $2$ meters long and $1$ meter wide, and hanjo (square mats) that are $1$ meter long and $1$ meter wide. Each tatami can be placed vertically or horizontally.
How many ways are there to fill the room?
We distinguish ways that match only after rotation or reflection.

Since the count can be enormous, find it modulo $998244353$.

Constraints

• $1 \leq H \leq 6$
• $1 \leq W \leq 10^{12}$

Input

Input is given from Standard Input in the following format:

$H$ $W$

Output

Print the answer.

Sample Input 1

2 2

Sample Output 1

7

We have the following seven ways:

Sample Input 2

3 3

Sample Output 2

131

Sample Input 3

5 100

Sample Output 3

379944232

Be sure to find the count modulo $998244353$.

update @ 2024/3/10 09:17:53