配点 : $600$ 点

問題文

長さ $N$ の整数列 $A = (A_1, \dots, A_N)$ が与えられます。

$(1, 2, \dots, N)$ を並べ替えて得られる列 $P = (P_1, \dots, P_N)$ であって、次の条件を満たすものの総数を $998244353$ で割った余りを求めてください。

• $A_{P_i} \lt A_{P_{i + 1}}$ となるような $1$ 以上 $N-1$ 以下の整数 $i$ がちょうど $K$ 個存在する。

制約

• $2 \leq N \leq 5000$
• $0 \leq K \leq N - 1$
• $1 \leq A_i \leq N \, (1 \leq i \leq N)$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_1$ $\ldots$ $A_N$

出力

答えを出力せよ。

4 2
1 1 2 2

4

$P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3)$ の $4$ 通りが条件を満たします。

10 3
3 1 4 1 5 9 2 6 5 3

697112