← 返回题目列表

AtCoder · arc166_c

C. LU / RD 标记

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

分数: 600 点

问题陈述

有一个网格 H 行和 W 列。

该网格有 H(W+1) 垂直边缘和 W(H+1) 水平边,总共 H(W+1) + W(H+1) (另请参阅示例输入/输出中的图)。考虑通过以下两种操作来标记这些边缘。

  • 操作(1):执行此操作时选择左边缘和上边缘未标记的正方形。标记该正方形的左边缘和上边缘。
  • 操作(2):执行此操作时,选择右边缘和下边缘未标记的正方形。标记该正方形的右边缘和下边缘。

求模数 998244353,当操作 (1) 和 (2) 可以执行任意次数(可能为零)时最终标记的可能的边集。

你有 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- 第行应包含数字,模数 998244353,最终标记为的可能的边集 i- 第一个测试用例。


示例输入 1

2
1 1
2 3

示例输出 1

4
800

对于这种情况 (H, W)=(1,1),最终标记有四组可能的边,如下所示。标记的边缘以粗体绘制。

对于这种情况 (H, W)=(2,3),以下一组标记的边缘是 可能:

另一方面,以下标记边缘组是 不可能:


示例输入 2

3
123 456
654 321
1000000 1000000

示例输出 2

60549740
298307903
656009181