这是问题的简单版本。两个版本之间的唯一区别是 $$$k$$$ 的约束以及 $$$k$$$ 的总和。
在古波斯,聪明的商人兼数学家海亚姆正在用他珍贵的宝箱玩游戏,宝箱里有 $$$n$$$ 红宝石,每颗价值 $$$2$$$ 第纳尔,$$$m$$$ 蓝色蓝宝石,每颗价值 $$$1$$$ 第纳尔。他还有一个书包,一开始是空的,$$$k$$$ 滚动成对 $$$(r_1, b_1), (r_2, b_2), \ldots, (r_k, b_k)$$$ 描述特殊情况。
$$$n + m$$$ 轮的游戏进行如下:
1. 海亚姆从宝箱中均匀随机抽取一颗宝石。
2. 他从箱子中取出宝石并将其放入背包中。
3. 如果存在一个卷轴 $$$i$$$ ($$$1 \leq i \leq k$$$),并且箱子中正好包含 $$$r_i$$$ 红色红宝石和 $$$b_i$$$ 蓝色蓝宝石,Khayyam 会收到一项皇家法令,将其背包中所有宝石的价值加倍,作为实现特殊配置的奖励。
请注意,某些宝石的价值可能会受到多个法令的影响,在这种情况下,宝石的价值会翻倍多次。
确定游戏结束时海亚姆背包的预期价值,以 $$$998,244,353$$$ 为模。
正式地,让 $$$M = 998,244,353$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 500$$$) — 红宝石的数量、蓝色蓝宝石的数量和分别描述特殊情况的卷轴。
接下来的 $$$k$$$ 行包含两个整数 $$$r_i$$$、$$$b_i$$$ ($$$0 \leq r_i \leq n$$$、$$$0 \leq b_i \leq m$$$、$$$1 \leq r_i + b_i \leq n+m-1$$$)。保证 $$$(r_i, b_i)$$$ 是不同的。
保证所有测试用例的$$$n$$$总和和$$$m$$$总和不超过$$$2 \cdot 10^5$$$,并且所有测试用例的$$$k$$$总和不超过$$$500$$$。
输出
对于每个测试用例,打印一个整数:进程结束时 Khayyam 书包的预期值,以 $$$998,244,353$$$ 为模。
示例
输入 #1
5 3 4 0 1 1 1 1 0 3 3 2 1 1 2 2 3 3 2 2 1 1 2 10 4 5 1 0 8 0 6 4 0 2 7 4
输出 #1
10 499122180 798595498 149736666 414854846
注意
在第一个测试用例中,在流程结束时,总会有 $$$3$$$ 红色红宝石和 $$$4$$$ 蓝色蓝宝石。卷轴中描述的特殊条件均未满足,因此海亚姆挎包的价值保持不变。最后书包的总价值始终为 $$$2 \cdot 3 + 1 \cdot 4 = 10$$$。
在第二个测试用例中,考虑以下两种情况:
- 海亚姆以 $$$1/2$$$ 的概率抽到一颗红宝石,他的书包的价值变为 $$$2$$$。然后,他以 $$$1$$$ 的概率抽到一颗蓝色蓝宝石,他的书包的价值变为 $$$3$$$。
- 海亚姆以 $$$1/2$$$ 的概率抽出一颗蓝宝石,他的书包的价值变为 $$$1$$$。此时,宝箱中包含 $$$r_1 = 1$$$ 红色红宝石和 $$$b_1 = 0$$$ 蓝色蓝宝石,这与卷轴中描述的特殊情况相符。结果,书包的价值翻倍为 $$$2 \cdot 1 = 2$$$。然后,他以 $$$1$$$ 的概率抽到一颗红宝石,他的书包的价值变为 $$$4$$$。
因此,最后的预期值为 $$$\frac{1}{2} \cdot 3 + \frac{1}{2} \cdot 4 = \frac{7}{2}$$$,即 $$$499,122,180$$$ 模 $$$998,244,353$$$。