题目描述

给定长度为 $N$ 的整数序列 $A = (A_1, \\dots, A_N)$。

找到满足以下条件的置换 $P = (P_1, \\dots, P_N)$ 的数量（模 $998244353$）：

• 存在恰好 $K$ 个整数 $i$，满足 $1 \\leq i \\leq N-1$，且 $A_{P_i} \\lt A_{P_{i+1}}$。

约束条件

• $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$

输出

输出结果到标准输出。

示例输入 1

4 2
1 1 2 2

示例输出 1

4

满足条件的置换有四种：$P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3)$。

示例输入 2

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

示例输出 2

697112