Gats and the Lonely Charms

Time limit: 3000 msMemory limit: 256 MB

Gats has a string carrying $N$ charms in a fixed left-to-right order. The color of the $i$ -th charm is $A_i$ .

There are $N-1$ gaps between consecutive charms. Gats selects exactly $K-1$ distinct gaps uniformly at random from all such selections and cuts the string at those gaps. This creates exactly $K$ nonempty pieces. When $K=1$ , no gap is selected.

For a piece $P$ , a color is called lonely in $P$ if exactly one charm of that color belongs to $P$ . Let $q(P)$ be the number of lonely colors in $P$ . The score of the complete cutting is

S=\sum_P q(P)^2,

where the sum is over all $K$ pieces.

Find the expected value of $S$ .

Input

The first line contains two integers $N$ and $K$ ( $1 \le K \le N \le 6000$ ), the number of charms and the required number of pieces.

The second line contains $N$ integers (), where is the color of the -th charm.

Output

Print one integer: the expected total score modulo $998244353$ .

Formally, if the expected score is the reduced fraction $x/y$ , print $x\cdot y^{-1}\bmod 998244353$ , where is the multiplicative inverse of modulo . The required inverse is guaranteed to exist.

Samples

Sample 1

Input

4 2
1 2 1 3

Output

665496242

There are three possible cut locations. They produce total scores $10$ , $8$ , and $2$ , so the expected score is $20/3$ . Its value modulo $998244353$ is $665496242$ .

Gats and the Lonely Charms

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2