Это сложная версия задачи. Единственное различие между двумя версиями — это ограничения на \(n\) и \(x\). Вы можете делать взломы, только если обе версии задачи решены.
Little09 давно интересуется магией, и как же ему повезло, что он встречает фокусника! Фокусник выполнит \(n\) операций, каждая из которых является одной из следующих трех:
- \(1\ x\): Создать свинью с \(x\) очками здоровья.
- \(2\ x\): Уменьшить очки здоровья всех живых свиней на \(x\).
- \(3\): Повторить все предыдущие операции. Формально, предполагая, что это \(i\)-я операция в последовательности операций, выполните по очереди первые \(i-1\) операций (включая операции «Повторить»).
Свинья умирает, когда ее очки здоровья становятся меньше или равны \(0\).
Little09 хочет знать, сколько живых свиней осталось после всех операций. Пожалуйста, выведите ответ по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — количество живых свиней после всех операций, по модулю \(998\,244\,353\).
Примечание
В первом примере операции эквивалентны повторению следующего четыре раза: создать свинью с \(8\) очками здоровья, а затем уменьшить очки здоровья всех живых свиней на \(3\). Легко видеть, что в конце остаются две живые свиньи с \(2\) и \(5\) очками здоровья.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 8
2 3
3
3
|
2
|
|
2
|
6
1 5
1 6
2 2
3
1 4
3
|
5
|
|
3
|
12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3
|
17
|