问题描述

Snuke 收到一个排列 $P=(P_1,P_2,\cdots,P_N)$，以及一个整数 $K$。他对 $P$ 进行了一些相邻元素的交换，以满足以下条件。

• 对于每个 $1 \leq i \leq N$，存在至多 $K$ 个满足 $1 \leq j < i$ 且 $P_j > P_i$ 的下标 $j$。

在这里，他进行的交换次数是最小次数，以满足此条件。

之后，他遗忘了自己收到的原始排列。给定交换后的排列 $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$，存在至多 $K$ 个满足 $1 \leq j < i$ 且 $P'_j > P'_i$ 的下标 $j$。
• 输入中的所有值都是整数。

输入

从标准输入读入数据，格式如下：

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

输出

打印答案。

示例输入 1

3 1
3 1 2

示例输出 1

2

$P$ 可能是以下两个排列之一：

• $P=(3,1,2)$：需要进行的最小交换次数为 $0$。经过 $0$ 次交换后，排列等于 $P'$。
• $P=(3,2,1)$：需要进行的最小交换次数为 $1$：交换 $P_2$ 和 $P_3$ 的位置，得到 $P=(3,1,2)$，满足条件且等于 $P'$。

示例输入 2

4 3
4 3 2 1

示例输出 2

1

示例输入 3

5 2
4 2 1 5 3

示例输出 3

3