#P18197. 012 Grid

012 Grid

012 Grid

给定一个 HH 行、WW 列的网格。你需要给每个格子恰好填入一个整数。记从上往下第 hh 行、从左往右第 ww 列所填的整数为 Xh,wX_{h,w}。

请计算满足以下所有条件的填法数:

  • 对于所有合法的 h,wh,w,有 Xh,w∈{0,1,2}X_{h,w}\in\{0,1,2\}。
  • 对于 1≤h<H1\le h<H、1≤w≤W1\le w\le W,有 Xh+1,w−Xh,w∈{0,1}X_{h+1,w}-X_{h,w}\in\{0,1\}。
  • 对于 1≤h≤H1\le h\le H、1≤w<W1\le w<W,有 Xh,w+1−Xh,w∈{0,1}X_{h,w+1}-X_{h,w}\in\{0,1\}。
  • 对于 1≤h<H1\le h<H、1≤w<W1\le w<W,有 Xh+1,w+1−Xh,w∈{0,1}X_{h+1,w+1}-X_{h,w}\in\{0,1\}。

也就是说,向下、向右、向右下方一步,数值都只能保持不变或增加 11。答案对 998244353998244353 取模。

输入格式

一行两个整数 H,WH,W,满足 1≤H,W≤2×1051\le H,W\le2\times10^5。

输出格式

输出一个整数,表示合法填法数对 998244353998244353 取模的结果。

样例 1

输入:

2 2

输出:

11

这 1111 种填法中,下面三种都是合法的。每块两行两列表示一份独立填法。

00    01    11
00    11    22

样例 2

输入:

20 23

输出:

521442928

样例 3

输入:

200000 200000

输出:

411160917