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}$。