配点 : $800$ 点

問題文

すぬけくんは，$(1,\ 2,\ ...\ N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ と整数 $K$ をもらいました． そこですぬけくんは，$P$ の隣接する二項をswapすることを繰り返して，以下の条件が満たされるようにしました．

• それぞれの $1 \leq i \leq N$ について， $1 \leq j< i$, $P_j>P_i$ を満たす $j$ が高々 $K$ 個である．

ここで，すぬけくんは最小の操作回数でこの条件を達成しました．

すべての操作が終わったあと，すぬけくんは元の順列を忘れてしまいました． 操作後の順列 $P'$ が与えられるので，元の順列 $P$ としてあり得るものが何通りあるかを $998244353$ で割った余りを求めてください．

制約

• $2 \leq N \leq 5000$
• $1 \leq K \leq N-1$
• $1 \leq P'_i \leq N$
• $P'_i \neq P'_j$ ($i \neq j$)
• それぞれの $1 \leq i \leq N$ について， $1 \leq j< i$, $P'_j>P'_i$ を満たす $j$ が高々 $K$ 個である
• 入力される値はすべて整数である

入力

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

$N$ $K$

$P'_1$ $P'_2$ $\cdots$ $P'_N$

出力

答えを出力せよ．

3 1
3 1 2

2

$P$ として考えられるのは以下の $2$ 通りです．

• $P=(3,1,2)$: 最小の操作回数は $0$ 回です．操作後の順列は $P'$ に一致します．
• $P=(3,2,1)$: 最小の操作回数は $1$ 回です．$P_2$ と $P_3$ をswapすることで，$P=(3,1,2)$ となり，これは条件を満たします．操作後の順列は $P'$ に一致します．

4 3
4 3 2 1

1

5 2
4 2 1 5 3

3