Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Let $B$ be an array of length $M$ consisting of positive integers.

In one operation, you may choose a non-empty subsequence$^\dagger$ of indices $1 \le i_1 < i_2 < \dots < i_k \le M$ such that the values $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ are pairwise distinct, and then decrease each chosen value by $1$.

Define the score of $B$, denoted by $\text{score}(B)$, as the minimum number of operations needed to make every element of $B$ equal to $0$.

You are given an array $A$ of length $N$.

Find the sum of score over all the non-empty subsequences of $A$.

Since the value might be large, output it modulo $998\,244\,353$.

$^\dagger$ A sequence $C$ is called a subsequence of a sequence $D$ if it can be obtained from $D$ by deleting several elements, possibly none or all of them, without changing the order of the remaining elements.

Input

The input is given in the following format:

T
N
A_1 A_2 ... A_N
:
  • All input values are integers.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le A_i \le 10^9$
  • It is guaranteed that the sum of $N^2$ over all test cases does not exceed $5000^2$.

Output

For each test case, output a single integer — the sum of score over all the non-empty subsequences of $A$, modulo $998\,244\,353$.

Examples

Sample Input 1

3
1
5
3
1 1 3
4
2 2 2 2

Sample Output 1

5
16
47

Note

Test case 1: The only non-empty subsequence is $[5]$, with score $5$. Therefore, the answer is $5$.

Test case 2: The non-empty subsequences of $[1, 1, 3]$ are:

  • two subsequences equal to $[1]$, each with score $1$,
  • $[3]$, with score $3$,
  • $[1, 1]$, with score $2$,
  • two subsequences equal to $[1, 3]$, each with score $3$,
  • $[1, 1, 3]$, with score $3$.

So, the total sum is $16$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.