[ABC267G] Increasing K Times

**题目描述** 给定一个正整数序列 $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)$。

[problemUrl]: https://atcoder.jp/contests/abc267/tasks/abc267_g 長さ $ 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 $

答えを出力せよ。

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 $ 通りが条件を満たします。