Description

如果一个排列对于每个 $1 \leq i \leq N$，最多只存在 $K$ 个 $j$ 使得 $1 \leq j < i$ 时 $P^{'}_j > P^{'}_i$ ，那么这就是一个好排列。

假设你原本有一个排列 $P$，通过每次交换相邻两个元素的方式，进行了最小的次数得到了好排列 $P^{'}$。

得到 $P^{'}$ 后，原本的排列 $P$ 却丢失了。现在给定 $P^{'}$ 和 $K$，希望你求出可能的原排列 $P$ 的个数。由于这个结果可能很大，所以求这个结果对 $998244353$ 取模。

Format

Input

第一行有两个整数 $N, K$ $(2 \leq N \leq 5000, 1 \leq K \leq N - 1)$。

第二行有 $N$ 个整数 $P^{'}_1, P^{'}_2, \cdots, P^{'}_N$ $(1 \leq P^{'}_i \leq N, P^{'}_i \ne P^{'}_j(i \ne j))$。

对于每个 $1 \leq i \leq N$，最多只存在 $K$ 个 $j$ 使得 $1 \leq j < i$ 时 $P^{'}_j > P^{'}_i$。

Output

输出一个整数，表示可能的原排列的个数对 $998244353$ 取模的结果。

Samples

3 1
3 1 2

2

Note

$P$ 应该是以下两种排列之一：

• $P=(3, 1, 2)$：所需的最小交换次数为 $0$。$0$ 次交换后，排列等于 $P^{'}$；
• $P=(3, 2, 1)$：所需的最小交换次数为 $1$：交换 $P_2$ 和 $P_3$ 得到 $P=(3, 1, 2)$，满足条件，等于$P^{'}$。

4 3
4 3 2 1

1

5 2
4 2 1 5 3

3

Limitation

1s, 1024KiB for each test case.