AT_arc202_b [ARC202B] Japanese "Knight's Tour"

题目描述

有一个 $H$ 行 $W$ 列的将棋棋盘,还有一个桂马棋子。令 $(i-1,j-1)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。(注意值被改变了 $1$)。 棋盘是一个环面,意味着上面和下面是连通的,左边和右边是连通的。位于 $(i,j)$ 的桂马可以移动到 $((i-2)\bmod H,(j-1)\bmod W)$ 或 $((i-2)\bmod H,(j+1)\bmod W)$。 满足以下条件的对桂马的移动称做**巡游**。 - 初始时将桂马放在 $(0,0)$。然后,移动桂马 $H\times W$ 使得桂马到达每个格子恰一次。最终桂马回到 $(0,0)$。 求不同的巡游的个数,对 $998244353$ 取模。两个巡游不同当且仅当存在一个整数 $i(1\le i\le H\times W)$,第 $i$ 次移动到达的格子不同。

输入格式

一行两个整数 $H,W$。

输出格式

一行一个整数,表示不同巡游的个数对 $998244353$ 取模的结果。

说明/提示

**数据范围** - $3\le H\le 2\times 10^5$ - $3\le W\le 2\times 10^5$ - 输入均为整数。 **样例 1 解释** $(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)$ 是满足条件的一个巡游。 总共有六种不同的巡游。