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: Khayyam draws a gem uniformly at random from the chest. He removes the gem from the chest and places it in his satchel. 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}). 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 d