Это сложная версия задачи. В двух версиях отличаются ограничения на $$$k$$$ и на сумму $$$k$$$.
В древней Персии Хайям, умный купец и математик, играет в игру со своим драгоценным сундуком с сокровищами. Сундук содержит $$$n$$$ красных рубинов стоимостью $$$2$$$ динара каждый и $$$m$$$ синих сапфиров стоимостью $$$1$$$ динар каждый. У него также есть мешок, в котором изначально ничего нет, и $$$k$$$ свитков с парами $$$(r_1, b_1), (r_2, b_2), \ldots, (r_k, b_k)$$$, описывающими особые состояния.
Игра состоит из $$$n + m$$$ таких ходов:
- Хайям случайно равновероятно достает драгоценный камень из сундука.
- Он кладет данный камень в свой мешок.
- Если существует свиток $$$i$$$ ($$$1 \leq i \leq k$$$), для которого в сундуке находятся ровно $$$r_i$$$ красных рубинов и $$$b_i$$$ синих сапфиров, то по королевскому указу стоимость всех драгоценных камней в его мешке удваивается в качестве награды за достижение особого состояния.
Обратите внимание, что стоимость некоторых драгоценных камней может быть изменена несколькими указами, и тогда она удваивается несколько раз.
Определите математическое ожидание стоимости камней в мешке Хайяма в конце игры по модулю $$$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 5000$$$) — количество красных рубинов, количество синих сапфиров и количество свитков, описывающих особые состояния, соответственно.
Каждая из следующих $$$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$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Для каждого набора входных данных выведите одно целое число: математическое ожидание стоимости камней в мешке Хайяма в конце процесса по модулю $$$998,244,353$$$.
53 4 01 1 11 03 3 21 12 23 3 22 11 210 4 51 08 06 40 27 4
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$$$.
