F2. Khayyam's Royal Decree (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only differences between the two versions are the constraints on $$$k$$$ and the sum of $$$k$$$.

In ancient Persia, Khayyam, a clever merchant and mathematician, is playing a game with his prized treasure chest containing $$$n$$$ red rubies worth $$$2$$$ dinars each and $$$m$$$ blue sapphires worth $$$1$$$ dinar each. He also has a satchel, which starts empty, and $$$k$$$ scrolls with pairs $$$(r_1, b_1), (r_2, b_2), \ldots, (r_k, b_k)$$$ that describe special conditions.

The game proceeds for $$$n + m$$$ turns as follows:

  1. Khayyam draws a gem uniformly at random from the chest.
  2. He removes the gem from the chest and places it in his satchel.
  3. If there exists a scroll $$$i$$$ ($$$1 \leq i \leq k$$$) such that the chest contains exactly $$$r_i$$$ red rubies and $$$b_i$$$ blue sapphires, Khayyam receives a royal decree that doubles the value of all the gems in his satchel as a reward for achieving a special configuration.

Note that the value of some gems might be affected by multiple decrees, and in that case the gems' value is doubled multiple times.

Determine the expected value of Khayyam's satchel at the end of the game, modulo $$$998,244,353$$$.

Formally, let $$$M = 998,244,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 5000$$$) — the number of red rubies, the number of blue sapphires, and the number of scrolls describing special conditions, respectively.

Each of the next $$$k$$$ lines contains two integers $$$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$$$). It is guaranteed that the pairs $$$(r_i, b_i)$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$, and the sum of $$$k$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, print a single integer: the expected value of Khayyam's satchel at the end of the process, modulo $$$998,244,353$$$.

Example
Input
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
Output
10
499122180
798595498
149736666
414854846
Note

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$$$.