Нехай $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$.