← 返回题目列表

AtCoder · arc139_e

E. 瓦齐尔

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

分数: 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