D. Хлеба и зрелищ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Taylor Swift - Love Story (Taylor's Version)
⠀

$$$n$$$ человек расположены на позициях $$$p_1, p_2, \ldots, p_n$$$ на одномерной координатной оси. Изначально $$$p_i = i$$$ для каждого $$$1 \leq i \leq n$$$.

Вы можете устроить зрелище на некоторой целочисленной координате $$$x$$$ ($$$1 \le x \le n$$$), и тогда все люди будут двигаться ближе к зрелищу, чтобы посмотреть на него.

Формально, если вы устроите зрелище на позиции $$$x$$$ ($$$1 \le x \le n$$$), происходят следующие изменения для каждого человека $$$i$$$ ($$$1 \le i \le n$$$):

  • если $$$p_i = x$$$, изменений нет;
  • если $$$p_i \lt x$$$, человек движется в положительном направлении, и $$$p_i$$$ увеличивается на $$$1$$$;
  • если $$$p_i \gt x$$$, человек движется в отрицательном направлении, и $$$p_i$$$ уменьшается на $$$1$$$.

Вы можете устраивать зрелища любое конечное количество раз и в любом порядке.

Можно доказать, что все позиции людей всегда остаются в пределах диапазона $$$[1, n]$$$, т.е. $$$1 \le p_i \le n$$$ в любое время.

Каждая позиция $$$x$$$ ($$$1 \le x \le n$$$) имеет значение $$$a_x$$$, связанное с ней. Оценка массива позиций $$$[p_1, p_2, \ldots, p_n]$$$, обозначаемая как $$$score(p)$$$, равна $$$\sum_{i = 1}^{n} a_{p_i}$$$, т.е. ваша оценка увеличивается на $$$a_x$$$ за каждого человека, стоящего на $$$x$$$ в конце.

Среди всех возможных различных массивов позиций $$$p$$$, которые могут быть получены с помощью организации зрелищ, найдите сумму $$$score(p)$$$. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел — $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

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

Для каждого набора входных данных выведите на отдельной строке сумму $$$score(p)$$$ по всем возможным различным массивам позиций $$$p$$$, которые могут быть получены с помощью организации зрелищ, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
7
1
1
2
5 10
3
1 1 1
4
1 1 1 1
4
10 2 9 7
5
1000000000 1000000000 1000000000 1000000000 1000000000
8
100 2 34 59 34 27 5 6
Выходные данные
1
45
24
72
480
333572930
69365
Примечание

В первом наборе входных данных единственным возможным результатом является то, что человек $$$1$$$ остается на $$$1$$$. Оценка этого массива равна $$$a_1 = 1$$$.

Во втором наборе входных данных возможны следующие массивы позиций $$$[p_1, p_2]$$$:

  • $$$[1, 2]$$$, оценка $$$15$$$;
  • $$$[1, 1]$$$, оценка $$$10$$$;
  • $$$[2, 2]$$$, оценка $$$20$$$.

Сумма оценок равна $$$15 + 10 + 20 = 45$$$.

В третьем наборе входных данных возможны следующие массивы позиций $$$[p_1, p_2, p_3]$$$:

  • $$$[1, 1, 1]$$$;
  • $$$[1, 1, 2]$$$;
  • $$$[1, 2, 2]$$$;
  • $$$[1, 2, 3]$$$;
  • $$$[2, 2, 2]$$$;
  • $$$[2, 2, 3]$$$;
  • $$$[2, 3, 3]$$$;
  • $$$[3, 3, 3]$$$.

Каждый из них имеет оценку $$$3$$$, и таким образом общая сумма равна $$$24$$$.