Пусть $B$ — массив длины $M$, состоящий из положительных целых чисел.
За одну операцию вы можете выбрать непустую подпоследовательность$^\dagger$ индексов $1 \le i_1 < i_2 < \dots < i_k \le M$ так, чтобы значения $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ были попарно различны, а затем уменьшить каждое выбранное значение на $1$.
Определим оценку массива $B$, обозначаемую как $\text{score}(B)$, как минимальное количество операций, необходимое для того, чтобы сделать каждый элемент массива $B$ равным $0$.
Вам дан массив $A$ длины $N$.
Найдите сумму оценок по всем непустым подпоследовательностям массива $A$.
Поскольку это значение может быть большим, выведите его по модулю $998\,244\,353$.
$^\dagger$ Последовательность $C$ называется подпоследовательностью последовательности $D$, если её можно получить из $D$ удалением нескольких элементов (возможно, ни одного или всех) без изменения порядка оставшихся элементов.
Входные данные
Входные данные даны в следующем формате:
T N A_1 A_2 ... A_N :
- Все входные значения — целые числа.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Гарантируется, что сумма $N^2$ по всем наборам входных данных не превосходит $5000^2$.
Выходные данные
Для каждого набора входных данных выведите одно целое число — сумму оценок по всем непустым подпоследовательностям массива $A$ по модулю $998\,244\,353$.
Примеры
Пример ввода 1
3 1 5 3 1 1 3 4 2 2 2 2
Пример вывода 1
5 16 47
Примечание
Набор входных данных 1: Единственная непустая подпоследовательность — $[5]$, её оценка равна $5$. Следовательно, ответ равен $5$.
Набор входных данных 2: Непустыми подпоследовательностями массива $[1, 1, 3]$ являются:
- две подпоследовательности, равные $[1]$, каждая с оценкой $1$,
- $[3]$ с оценкой $3$,
- $[1, 1]$ с оценкой $2$,
- две подпоследовательности, равные $[1, 3]$, каждая с оценкой $3$,
- $[1, 1, 3]$ с оценкой $3$.
Таким образом, общая сумма равна $16$.