CF2034F2 Khayyam's Royal Decree (Hard Version)

这是本题的困难版本。两个版本的唯一区别在于 $k$ 和 $\sum k$ 的限制。 Khayyam 有一个**宝箱**，**宝箱**里初始有 $n$ 个红宝石和 $m$ 个蓝宝石。一个红宝石的价值为 $2$，一个蓝宝石的价值为 $1$。他还有一个**背包**，初始为空。另外，他还有 $k$ 张卷轴，第 $i$ 张卷轴上有数对 $(r_i,b_i)$。 Khayyam 将进行一个游戏，游戏共 $n+m$ 轮，每轮流程如下： 1. Khayyam 从**宝箱**中等概率随机拿出一个宝石。 2. 他将这个宝石放入**背包**中。 3. 若存在一张卷轴 $i$，使得**宝箱**中恰有 $r_i$ 个红宝石和 $b_i$ 个蓝宝石，将所有**背包**里的宝石的价值翻倍。 一个宝石的价值可以被多次翻倍。 求游戏结束时 Khayyam **背包**里宝石的价值总和的期望值，对 $998244353$ 取模。

多测，第一行一个整数 $T$ 表示数据组数。 每组数据的第一行三个整数 $n,m,k$。 接下来 $k$ 行，每行两个整数 $r_i,b_i$。 保证 $1\le T\le 500$，$1\le n,m,\sum n,\sum m\le 2\times 10^5$，$1\le k,\sum k\le 5000$。 保证 $0\le r_i\le n$，$0\le b_i\le m$，$1\le r_i+b_i\le n+m-1$，且 $(r_i,b_i)$ 两两不同。

一行一个整数，表示答案对 $998244353$ 取模的值。 ### 样例解释 对于第一组数据，最终背包里总会有 $3$ 个红宝石和 $4$ 个蓝宝石，不会有卷轴被触发。因此背包里宝石的总价值总是 $2\times 3+1\times 4=10$。 对于第二组数据： + 有 $\dfrac{1}{2}$ 概率，Khayyam 先拿出红宝石再拿出蓝宝石，不会有卷轴被触发，总价值为 $3$； + 有 $\dfrac{1}{2}$ 概率，Khayyam 先拿出蓝宝石再拿出红宝石，卷轴 $1$ 会被触发，蓝宝石的价值翻倍，总价值为 $4$。 因此总价值的期望是 $\dfrac{1}{2}\times 3+\dfrac{1}{2}\times 4=\dfrac{7}{2}\equiv 499122180\pmod {998244353}$。

In the first test case, at the end of the process, there will always be $ 3 $ red rubies and $ 4 $ blue sapphires. None of the special conditions described in the scrolls are met, so the value of Khayyam's satchel remains unchanged. The total value of the satchel at the end is always $ 2 \cdot 3 + 1 \cdot 4 = 10 $ . In the second test case, consider the following two cases: - With probability $ 1/2 $ , Khayyam draws a red ruby, and the value of his satchel becomes $ 2 $ . Then with probability $ 1 $ , he draws a blue sapphire, and the value of his satchel becomes $ 3 $ . - With probability $ 1/2 $ , Khayyam draws a blue sapphire, and the value of his satchel becomes $ 1 $ . At this point, the chest contains $ r_1 = 1 $ red rubies and $ b_1 = 0 $ blue sapphires, which match the special condition described in a scroll. As a result, the value of the satchel is doubled to $ 2 \cdot 1 = 2 $ . Then with probability $ 1 $ , he draws a red ruby, and the value of his satchel becomes $ 4 $ . Thus, the expected value at the end is $ \frac{1}{2} \cdot 3 + \frac{1}{2} \cdot 4 = \frac{7}{2} $ , which is $ 499,122,180 $ modulo $ 998,244,353 $ .