← 返回题目列表

AtCoder · arc202_b

B. 日本《骑士之旅》

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

分数: 800 点

问题陈述

有一个将棋(日本象棋)棋盘,上面有 H 行和 W 柱子,以及一件骑士棋子。广场位于 i从顶部数第行和 j板左侧的第列表示为 (i-1, j-1)。 (请注意,这些值移动了 1.)
这块板是一个环面,意思是上下相连,左右相连。一位骑士在 (i, j) 可以移至 ((i-2) \bmod H, (j-1) \bmod W) or ((i-2) \bmod H, (j+1) \bmod W)。 (请注意,这与标准国际象棋中的马不同。)

移动棋盘上的马以满足以下条件称为 游览.

  • 最初,将骑士放置在 (0, 0)。然后,移动骑士 H \times W 次,以便骑士恰好访问每个方格一次。最后,骑士回归 (0, 0).

求旅游次数模数 998244353。当且仅当存在一个整数时,两个旅行被认为是不同的 i (1 \leq i \leq H\times W) 这样的目的地 i第一步动作不同。

约束

  • 3 \leq H \leq 2 \times 10^5
  • 3 \leq W \leq 2 \times 10^5
  • 所有输入值均为整数。

输入

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

H W

输出

输出旅游次数模数 998244353.


示例输入 1

3 3

示例输出 1

6

例如,运动 (0,0) \to (1,1) \to (2,2) \to (0,1) \to (1,2) \to (2,0) \to (0,2) \to (1,0) \to (2,1) \to (0,0) 满足旅游的条件。
总共有六个游览。


示例输入 2

123 45

示例输出 2

993644157

示例输入 3

6789 200000

示例输出 3

152401277