I2. Ласковые массивы (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Ирис хранит целочисленный массив $$$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$$$. Он обещает вам: если вы успешно поможете ему, он поделится с вами кусочком праздничного торта Ирис.

$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$d$$$, если $$$c$$$ может быть получен из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

$$$^{\text{†}}$$$Последовательность $$$c$$$ является подпоследовательностью $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^6$$$) — длина массива $$$a_1, a_2, \ldots, a_n$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — исходный массив. Гарантируется, что $$$\max(\lvert a_i\rvert) \leq \sum a_i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую целое число: сумму значений подходящих массивов $$$b_1, b_2, \ldots, b_m$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
4
1 2 3 4
4
2 -3 2 2
4
1 -2 2 1
10
2 -7 6 3 -1 4 2 -5 8 -4
20
4 -2 4 3 -2 1 5 2 3 6 -5 -1 -4 -2 -3 5 -3 1 -4 1
Выходные данные
1
2
2
20
1472
Примечание

В первом наборе входных данных $$$a=[1, 2, 3, 4]$$$. Единственный возможный массив $$$b$$$ — это $$$[1, 2, 3, 4]$$$, его значение равно $$$1$$$.

Во втором наборе входных данных $$$a=[2, -3, 2, 2]$$$. Возможными массивами $$$b$$$ являются $$$[1, 2, -3, 2, -1, 2]$$$ и $$$[2, 1, -3, 2, -1, 2]$$$, их значения равны $$$1$$$.

В третьем наборе $$$a=[1, -2, 2, 1]$$$. Единственный подходящий массив $$$b$$$ является $$$[1, 1, -2, 2, -1, 1]$$$. Его значение равно $$$2$$$, так как мы можем выбрать массивы $$$c=[1,3,4,6]$$$ или $$$[2,3,4,6]$$$. Таким образом, массив $$$a$$$ встречается в $$$b$$$ дважды, поэтому ответ $$$2$$$.