AT_abc204_f [ABC204F] Hanjo 2

题目描述

有一个长 $H$（$1≤H≤6$）米，宽 $W$ 米（$1≤W≤10^{12}$）的房间，现在用两种地板砖铺地板：长 $2$ 米，宽 $1$ 米的长方形地板砖和边长为 $1$ 米的正方形地板砖。

长方形地板砖可以旋转成长 $1$ 米，宽 $2$ 米的长方形地板砖。

求铺满这个房间的总方案数。

输入格式

一行两个整数 $H$ 和 $W$。

输出格式

一个数，表示总方案数，结果对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2 2

输出 #1

7

输入输出样例 #2

输入 #2

3 3

输出 #2

131

输入输出样例 #3

输入 #3

5 100

输出 #3

379944232

说明/提示

数据范围

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

样例解释 1

有以下七种方法：

样例解释 3

一定要对 $998244353$ 取模。