Alice and Bob are given an array of length of N. They decide to play a game with it.

Initially, Alice randomly shuffles the array, and then Bob takes N turns. In each turn, Bob chooses an index which he has not already chosen and then Alice reveals the number on that index to Bob. If this number is either the first number to be chosen or strictly larger than previously chosen numbers by Bob then he takes it and adds to his array else he throws it.

You only know the initial unshuffled array and want to know the expected length of Bob's array at the end of the game.

The final expected length can be represented as a fraction of the form \frac{P}{Q}. You are required to print P \cdot Q^{-1} \bmod 998244353.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains two lines of input.
- The first line contains N the length of the array.
- The second line contains N space-separated integers A_{1}, A_{2},..., A_{N} representing the initial array.

------ Output Format ------ 

For each testcase, output in a single line the expected length of Bob's array at the end of the game modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 2 \cdot 10^{4}$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 5 \cdot 10^{5}$
- Sum of $N$ does not exceeds $5 \cdot 10^{5}$ over all testcases.

----- Sample Input 1 ------ 
4
2
1 2
3
1 2 3
3
1 1 1
3
2 3 2
----- Sample Output 1 ------ 
499122178
831870296
1
665496237
----- explanation 1 ------ 
Test case $1$: The possible final arrays will be $[2, 1]$ or $[1, 2]$. If Bob chooses indexes in the order $[2, 1]$ then he will end up with $2$ elements in the first case and $1$ element in the second case, if he chooses indexes in the order $[1, 2]$ then he will end up with $1$ element in the first case and $2$ elements in the case. Hence his probability ending up with $2$ elements is $\frac{1}{2}$ and with $1$ element is also $\frac{1}{2}$. Hence the final answer will be calculated as $2 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2}$ which is equal to $\frac{3}{2}$.

Test case $2$: The probability of Bob ending up with all three elements is $\frac{1}{6}$, the probability that he ends up with any two elements is $\frac{1}{2}$ and the probability that he ends with only a single element is $\frac{1}{3}$. Hence the final answer is calculated as $3 \cdot \frac{1}{6} + 2 \cdot \frac{1}{2} + 1 \cdot \frac{1}{3}$ which is equal to $\frac{11}{6}$.

Test case $3$: No matter what index Bob chooses initially he will only end up with $1$ element in his final array. Hence the final expected value is equal to $1$.

Test case $4$: The probability of Bob ending up with all three elements is $0$, the probability that he ends up with any two elements is $\frac{2}{3}$ and the probability that he ends with only a single element is $\frac{1}{3}$. Hence the final answer is calculated as $2 \cdot \frac{2}{3} + 1 \cdot \frac{1}{3}$ which is equal to $\frac{5}{3}$.

Difficulty: VERY_HARD
Tags: Number theory

Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
modulo = 998244353

def shuffle(x):
	return pow(x, modulo - 2, modulo)
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	z = len(set(a))
	sort = shuffle(n)
	arr = [0] * n
	arr[-1] = 1
	num = 1
	for i in reversed(range(n - 1)):
		arr[i] = arr[i + 1] if a[i] == a[i + 1] else (1 + num * shuffle(n - i - 1)) % modulo
		num = (num % modulo + arr[i] % modulo) % modulo
	print(num * sort % modulo)


mod = 998244353

def invfac(x):
	return pow(x, mod - 2, mod)
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	x = len(set(a))
	den = invfac(n)
	dp = [0] * n
	dp[-1] = 1
	num = 1
	for i in reversed(range(n - 1)):
		dp[i] = dp[i + 1] if a[i] == a[i + 1] else (1 + num * invfac(n - i - 1)) % mod
		num = (num % mod + dp[i] % mod) % mod
	print(num * den % mod)