/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
縦 H マス、横 W マスの将棋盤と 1 個の桂馬の駒があります。将棋盤の上から i 行目、左から j 列目にあるマスを (i-1, j-1) と表します。(値が 1 ずれている点に注意してください。)
この将棋盤はトーラス、すなわち上と下および左と右がつながっています。(i, j) にある桂馬は ((i-2) \bmod H, (j-1) \bmod W) または ((i-2) \bmod H, (j+1) \bmod W) に動かすことができます。
次の条件を満たすように桂馬を将棋盤の上で動かすことを ツアー と呼びます。
- はじめ、(0, 0) に桂馬を置く。その後、桂馬が全てのマスにちょうど 1 回ずつ移動するように H \times W 回桂馬を動かす。そして最終的に桂馬が (0, 0) に戻ってくる。
ツアーが何通りあるかを 998244353 で割った余りを求めてください。ただし、2 つのツアーはある整数 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) という移動はツアーとして条件を満たします。
ツアーは全部で 6 通りあります。
入力例 2
123 45
出力例 2
993644157
入力例 3
6789 200000
出力例 3
152401277
Score : 800 points
Problem Statement
There is a shogi (Japanese chess) board with H rows and W columns, and one knight piece. The square at the i-th row from the top and j-th column from the left of the board is represented as (i-1, j-1). (Note that the values are shifted by 1.)
This board is a torus, meaning the top and bottom are connected, and the left and right are connected. A knight at (i, j) can move to ((i-2) \bmod H, (j-1) \bmod W) or ((i-2) \bmod H, (j+1) \bmod W). (Note that this is different from the knight in Standard chess.)
Moving the knight on the board to satisfy the following condition is called a tour.
- Initially, place the knight at (0, 0). Then, move the knight H \times W times so that the knight visits every square exactly once. Finally, the knight returns to (0, 0).
Find the number of tours modulo 998244353. Two tours are considered different if and only if there exists an integer i (1 \leq i \leq H\times W) such that the destination of the i-th move is different.
Constraints
- 3 \leq H \leq 2 \times 10^5
- 3 \leq W \leq 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
Output
Output the number of tours modulo 998244353.
Sample Input 1
3 3
Sample Output 1
6
For example, the movement (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) satisfies the conditions as a tour.
There are six tours in total.
Sample Input 2
123 45
Sample Output 2
993644157
Sample Input 3
6789 200000
Sample Output 3
152401277