/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 H 行，横 W 列のグリッドがあります．
このグリッドには縦向きの辺が H(W+1) 個，横向きの辺が W(H+1) 個，合計で H(W+1) + W(H+1) 個の辺があります（入出力例の図も参考にしてください）．これらの辺に対して，次の 2 種の操作によって印をつけることを考えます．
- 操作 (1)：操作を行う時点で左側の辺と上側の辺に印がついていないようなマスをひとつ選ぶ．そのマスの左側の辺と上側の辺に印をつける．
- 操作 (2)：操作を行う時点で右側の辺と下側の辺に印がついていないようなマスをひとつ選ぶ．そのマスの右側の辺と下側の辺に印をつける．
操作 (1) と操作 (2) を（0 回を含め）何回でも行えるとき，最終的に印がついている辺の集合としてありうるものの個数を 998244353 で割った余りを求めてください．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 2\times 10^5
- 1\leq H, W\leq 10^6
入力
入力は以下の形式で標準入力から与えられます．
T
\text{case}_1
\vdots
\text{case}_T
各テストケースは以下の形式で与えられます．
H W
出力
T 行出力してください．i 行目には i 番目のテストケースについて，最終的に印がついている辺の集合としてありうるものの個数を 998244353 で割った余りを出力してください．
入力例 1
2 1 1 2 3
出力例 1
4 800
(H, W)=(1,1) の場合には，最終的に印がついている辺の集合としてありうるのは次の 4 通りです．印がついている辺を太線で表しています．
(H, W)=(2,3) の場合には，例えば次のような辺の集合がありえます．
一方で，次のような辺の集合はありえません．
入力例 2
3 123 456 654 321 1000000 1000000
出力例 2
60549740 298307903 656009181
Score : 600 points
Problem Statement
There is a grid with H rows and W columns.
This grid has H(W+1) vertical edges and W(H+1) horizontal edges, for a total of H(W+1) + W(H+1) (see also the figures at Sample Input/Output). Consider marking these edges by the following two kinds of operations.
- Operation (1): Choose a square whose left and upper edges are unmarked when performing this operation. Mark the left and upper edges of that square.
- Operation (2): Choose a square whose right and lower edges are unmarked when performing this operation. Mark the right and lower edges of that square.
Find the number, modulo 998244353, of possible sets of edges that are eventually marked when Operations (1) and (2) can be performed any number of times, possibly zero.
You have T test cases to solve.
Constraints
- 1\leq T\leq 2\times 10^5
- 1\leq H, W\leq 10^6
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each test case is given in the following format:
H W
Output
Print T lines. The i-th line should contain the number, modulo 998244353, of possible sets of edges that are eventually marked for the i-th test case.
Sample Input 1
2 1 1 2 3
Sample Output 1
4 800
For the case (H, W)=(1,1), there are four possible sets of edges that are eventually marked, as shown below. The marked edges are drawn in bold.
For the case (H, W)=(2,3), the following sets of marked edges are possible:
On the other hand, the following sets of marked edges are impossible:
Sample Input 2
3 123 456 654 321 1000000 1000000
Sample Output 2
60549740 298307903 656009181