Это сложная версия задачи. В двух версиях отличаются ограничения на \(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}\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: математическое ожидание стоимости камней в мешке Хайяма в конце процесса по модулю \(998,244,353\).
Примечание
В первом наборе входных данных, в конце процесса всегда будет \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
10
499122180
798595498
149736666
414854846
|