Задача . I2. Ласковые массивы (сложная версия)

Обратите внимание, что данное условие отличается от условия, использованного в официальном раунде. Условие было исправлено на версию, имеющую решение. Все посылки по этой задачи в официальном раунде были удалены.

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вычислить сумму значений подходящих массивов. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Ирис хранит целочисленный массив \(a_1, a_2, \ldots, a_n\). Она знает, что этот массив обладает интересным свойством: максимальное абсолютное значение всех элементов меньше или равно сумме всех элементов, то есть \(\max(\lvert a_i\rvert) \leq \sum a_i\).

Ирис определяет скучность массива как максимальную сумму его подмассива\(^{\text{∗}}\).

Приближается день рождения Ирис, и Виктор собирается прислать ей ещё один массив \(b_1, b_2, \ldots, b_m\). По некоторым, казалось бы, очевидным причинам он решает, что массив \(b_1, b_2, \ldots, b_m\) должен обладать следующими свойствами.

• \(a_1, a_2, \ldots, a_n\) должен быть подпоследовательностью\(^{\text{†}}\) из \(b_1, b_2, \ldots, b_m\).
• Эти два массива имеют одинаковую сумму. То есть, \(\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i\).
• Значение скучности массива \(b_1, b_2, \ldots, b_m\) является наименьшим из возможных.
• Среди массивов с наименьшей скучностью длина массива \(b\) (т.е. \(m\)) является наименьшей из возможных. В этом случае Ирис поймёт его уважение как можно скорее!

Для массива \(b_1, b_2, \ldots, b_m\), удовлетворяющего условиям выше, Виктор определяет значение массива как количество вхождений массива \(a\) как подпоследовательности в массив \(b\). Другими словами, вычисляет количество массивов \(c_1, c_2, \ldots, c_{n}\) таких, что \(1\le c_1< c_2< \ldots< c_n\le m\), и для всех целых \(i\), удовлетворяющих \(1\le i\le n\), выполняется \(b_{c_{i}}=a_i\), и называет это число значением массива \(b\).

Даже при таких ограничениях, как указано выше, всё равно существует слишком много возможных подарков. Поэтому Виктор просит вас посчитать сумму значений подходящих массивов \(b_1, b_2, \ldots, b_m\), удовлетворяющих всем вышеприведенным условиям. Так как ответ может быть очень большим, Виктору нужно только это число по модулю \(998\,244\,353\). Он обещает вам: если вы успешно поможете ему, он поделится с вами кусочком праздничного торта Ирис.