Problem Statement

You are given positive integers $N, K$ and a sequence of positive integers $A_1, A_2, \ldots, A_N$ of length $N$.

Initialize all elements of an array $z = [z_1, z_2, \ldots, z_{N}]$ of length $N$ to 0, and then perform the following operation $K$ times.

1. Choose an integer $i \in \{1, 2, \ldots, N \}$ at random. Here, the probability that $i$ is chosen is $\frac{A_i}{\sum_{i=1}^{N}A_i}$, and the trials are independent for each operation.
2. For the chosen $i$, update $z_i \leftarrow z_i + 1$.

Let $S$ be the set of all non-negative integer arrays of length $N$, and for $x \in S$, let $f(x)$ be the probability that $z = x$ after the above operations are finished.
Compute $\max_{x \in S} f(x)$.

It can be proved under the constraints of this problem that $\max_{x \in S} f(x)$ can be expressed as an irreducible fraction $\frac{P}{Q}$, and that an integer $R$ satisfying $R \times Q \equiv P \ (\mathrm{mod}\ 998244353)$ and $0 \leq R < 998244353$ is uniquely determined. Output this $R$.

You are given $T$ test cases; solve each of them.

Input

$T$

$N$ $K$
$A_1 A_2 \ldots A_N$

Output

Output the value of $R$ on each line. Print a newline at the end.

Sample

3
2 2
1 1
3 1
2 3 3
5 10
31 41 59 26 53

499122177
623902721
484466660