题目描述

すぬけくんは，$(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$ で割った余りを求めてください．

输入格式

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

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

输出格式

答えを出力せよ．

题目大意

Snuke 有一个长度为 $n(1\le n\le5000)$ 的排列，他对它进行了如下操作：

• 交换两个相邻的数，直到对于每个 $i$ ，有至多 $k(1\le k \le n-1)$ 个 $j$ 满足 $1\le j<i$ 且 $p_j>p_i$。

他最小化了他的操作数，但是他忘记了一开始的序列是什么了。

现在给你他操作完了的排列和 $n,k$，问可能的原排列有多少种。答案对 $998244353$ 取模。

3 1
3 1 2

2

4 3
4 3 2 1

1

5 2
4 2 1 5 3

3

提示

制約

• $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$ 個である
• 入力される値はすべて整数である

Sample Explanation 1

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