Description

Bob likes drawing cards.

Bob recently started playing a card-drawing game called "Zhugong Link". There are $n$ different characters in the game, numbered from $1$ to $n$. If Bob obtains $k$ cards whose numbers are consecutive, he can form the theoretically strongest team.

In the current card pool, there are $m$ different cards. Each time he draws, Bob gets one card uniformly at random from the pool. If Bob draws a card he already owns, then nothing happens, which means this draw is wasted. Bob is a cautious person. He wants to know: if he keeps drawing until he has obtained $k$ cards with consecutive numbers and then stops, what is the expected number of draws needed.

Input Format

The first line contains two integers $m, k$.

The second line contains $m$ pairwise distinct integers $a_1, a_2, \cdots, a_m$, indicating which characters are in the card pool.

In this statement, $n$ is the maximum value among $a_i$.

Output Format

Output one integer in one line, representing the expected number of draws modulo $p = 998244353$. That is, if the expected value in lowest terms is $\frac{a}{b}$, you need to output an integer $c$ such that $c \times b \equiv a \pmod{p}$.

3 2
1 2 3

499122180

10 2
1 2 3 4 5 7 8 9 11 12

839792873

Hint

Sample Explanation 1

If the first draw is card $2$, then the expected number of draws is $1 + \frac{3}{2}$. If the first draw is card $1$ or card $3$, then the expected number of draws is $1 + 3$. Therefore the answer is $\frac{1}{3}(1 + \frac{3}{2}) + \frac{2}{3}(1 + 3) = 3.5$.

Constraints and Notes

For the first $10\%$ of the testdata, $m \le 10$.
For another $10\%$ of the testdata, $m \le 500$ and $k = m − 1$.
For another $10\%$ of the testdata, $m \le 500$ and it is guaranteed that there exists exactly one theoretically strongest team.
For another $10\%$ of the testdata, $m \le 500$ and it is guaranteed that any two theoretically strongest teams that can be drawn do not overlap.
For the first $50\%$ of the testdata, $m \le 500$.
For the first $70\%$ of the testdata, $m \le 5000$.
For another $10\%$ of the testdata, $k = 5$.
For another $10\%$ of the testdata, $k = 2000$.
For $100\%$ of the testdata, $1 \le m \le 200000, 1 \le a_i \le 2m, 2 \le k \le m$. It is guaranteed that there exists at least one theoretically strongest team that can be drawn (i.e., $k$ cards with consecutive numbers).

Translated by ChatGPT 5