分数: 800 点
问题陈述
我们有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
假设这个网格是一个环面;也就是说,除了水平或垂直彼此相邻的方格对之外,假设以下方格对彼此相邻。
- (i,1) 和 (i,W),对于每个整数 i 这样 1 \leq i \leq H.
- (1,j) 和 (H,j),对于每个整数 j 这样 1 \leq j \leq W.
考虑在网格中的方格上放置一定数量的棋子。这里,每个方格上最多可以有一个棋子,并且相邻方格上不能有两个棋子。
让 L 是可以放置的最大件数。求出路数,取模 998244353,放置 L 件。
约束
- 2 \leq H \leq 10^5
- 2 \leq W \leq 10^{10}
- H 和 W 是整数。
输入
输入由标准输入按以下格式给出:
H W
输出
打印答案。
样本输入 1
3 2
示例输出 1
6
以下六个放置满足条件。在这里, # 和 . 分别代表有和没有棋子的正方形。
#. #. .# .# .. .. .# .. #. .. #. .# .. .# .. #. .# #.
示例输入 2
139 424
示例输出 2
148734121
示例输入 3
12345 1234567890
示例输出 3
227996418