408811: GYM103328 H Mario Kart

A Mario Kart tournament consists of $$$N$$$ games. Each of the games is played by $$$M$$$ players. In each of the $$$N$$$ games, each of the $$$M$$$ players receives a rank according to the order they arrived at the goal. A player's record of the whole tournament could be represented as an array of $$$N$$$ numbers, $$$A = [a_1, a_2, ..., a_N]$$$, meaning that the player got $$$a_i$$$-th rank in the $$$i$$$-th game. To evaluate a player's performance, one could design a function $$$f$$$ satisfying $$$K \geq f(1) \geq f(2) \geq ... \geq f(M) \geq 1$$$, then further represent the player's performance as $$$\sum_{i=1}^{N} f(a_i)$$$. (Note that all $$$f(i)$$$ should be integers.)

For example, if $$$N = 2, M = 3, A = [1, 3]$$$ and $$$f(1) = 6, f(2) = 3, f(3) = 3$$$, then the performance of the player is equal to $$$f(1) + f(3) = 6 + 3 = 9$$$.

Ian just finished a Mario Kart tournament. Before the final result is announced by the judge, he would like to guess his rank in the tournament. However, he doesn't know how other players are performing, and the function $$$f$$$ for calculating the performance. Since there is no way to know his exact rank under this constraint, Ian decides to think about another problem.

Given the ranks he got in each of the games, he wants to calculate how many different ranking arrays could possibly have a strictly higher performance than his.

Two ranking arrays $$$A$$$ and $$$B$$$ are considered as different ranking arrays if and only if there exists some $$$i$$$ such that $$$a_i \not= b_i$$$. Note here that you should also consider the arrays with some $$$i$$$ such that $$$a_i = b_i$$$.

Since the answer could be very large, please output it modulo $$$998244353$$$.

The first line of the input consists of three integers $$$N$$$, $$$M$$$, and $$$K$$$, representing the number of rounds, the number of players in each round, and the range of the scoring function.

The second line of the input consists of $$$N$$$ integers $$$a_1, a_2, ..., a_N$$$, representing that Ian got $$$a_i$$$-th place in the $$$i$$$-th game.

• $$$1 \leq N, M, K \leq 3000$$$
• $$$1 \leq a_i \leq M$$$

Output a single line consists of a single integer, representing the number of different ranking arrays which could possibly score higher than Ian's.

3 3 3
1 1 2

1

3 3 3
3 3 3

26

3 3 3
2 2 2

19