← 返回题目列表

AtCoder · abc204_f

F. 半条 2

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个长方形的房间 H 米长并且 W 米宽。
我们将用榻榻米(矩形垫)填满整个房间 2 米长并且 1 米宽,和 hanjo(方形垫) 1 米长并且 1 米宽。每个榻榻米可以垂直或水平放置。
有多少种方法可以填满房间?
我们区分仅在旋转或反射后匹配的方式。

由于计数可能很大,请对它求模 998244353.

约束

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

输入

输入由标准输入按以下格式给出:

H W

输出

打印答案。


示例输入 1

2 2

示例输出 1

7

我们有以下七种方式:


示例输入 2

3 3

示例输出 2

131

示例输入 3

5 100

示例输出 3

379944232

一定要找到计数模数 998244353.