AT_agc054_c.[AGC054C] Roughly Sorted

すぬけくん得到了一个 $ (1,\ 2,\ ...,\ N) $ 的排列 $ P=(P_1,P_2,\cdots,P_N) $ 和一个整数 $ K $。于是，すぬけくん不断交换 $ P $ 中相邻的两个元素，使得满足以下条件：

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

在这里，すぬけくん以最小的操作次数达成了上述条件。

所有操作结束后，すぬけくん忘记了原来的排列。现在给定操作后的排列 $ P' $，请你求出有多少种可能的原始排列 $ P $，使得经过最小次数的相邻交换后可以得到 $ P' $，并将答案对 $ 998244353 $ 取模。

输入通过标准输入给出，格式如下：

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

请输出答案。

限制条件

• $ 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 $，满足 $ 1\leq j<i $ 且 $ P'_j>P'_i $ 的 $ j $ 的个数至多为 $ K $。
• 输入的所有值均为整数。

样例解释 1

作为 $ P $ 的可能有以下 $ 2 $ 种情况：

• $ P=(3,1,2) $：最小操作次数为 $ 0 $，操作后的排列与 $ P' $ 相同。
• $ P=(3,2,1) $：最小操作次数为 $ 1 $，交换 $ P_2 $ 和 $ P_3 $ 后得到 $ P=(3,1,2) $，满足条件，操作后的排列与 $ P' $ 相同。

由 ChatGPT 4.1 翻译