题目描述

長さ $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$ 個存在する。

输入格式

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

$N$ $K$ $A_1$ $\ldots$ $A_N$

输出格式

答えを出力せよ。

题目大意

题目描述

给定一个正整数序列 $A=(a_1,a_2,\ldots,a_n)$，问有多少个 $1\sim n$ 的排列 $P=(p_1,p_2,\ldots,p_n)$ 满足：

• 存在恰好 $k$ 个整数 $i(1\leqslant i\leqslant n-1)$ 满足 $a_{p_i}<a_{p_{i+1}}$

对 $998244353$ 取模。

输入格式

第一行两个整数 $n,k$，含义如题意所示。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

输出一个整数，表示满足条件的排列 $P$ 个数。

数据范围

$2\leqslant n\leqslant 5000,0\leqslant k\leqslant n-1,1\leqslant a_i\leqslant n$

样例解释

只有四个排列 $P$ 满足条件，分别是 $(1,3,2,4),(1,4,2,3),(2,3,1,4),(2,4,1,3)$。

4 2
1 1 2 2

4

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

697112

提示

制約

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

Sample Explanation 1

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