重排问题

题目描述

有 $N$ 个人，分别称为 Person $1$、Person $2$、$\dots$、Person $N$，从前到后按 $(1,2,\dots,N)$ 的顺序排成一列。Person $i$ 穿着颜色 $c_i$。

Takahashi 重复以下操作 $K$ 次：任意选择两个人 $i$ 和 $j$，交换 Person $i$ 和 Person $j$ 的位置。

在 $K$ 次操作全部结束后，对于每个满足 $1 \leq i \leq N$ 的整数 $i$，从前数第 $i$ 个人所穿的颜色都与 $c_i$ 一致。

经过这 $K$ 次操作后，人的排列有多少种可能？请输出答案对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出：

N K
c_1 c_2 … c_N

输出格式

输出答案。

样例

4 1
1 1 2 1

3

以下是 Takahashi 可能的操作以及每次操作后人的排列的完整列表。

• 交换 Person 1 和 Person 2 的位置，得到排列 $(2, 1, 3, 4)$。
• 交换 Person 1 和 Person 4 的位置，得到排列 $(4, 2, 3, 1)$。
• 交换 Person 2 和 Person 4 的位置，得到排列 $(1, 4, 3, 2)$。

3 3
1 1 2

1

下面是 Takahashi 可能执行的操作序列的一个例子。

• 第 1 次操作：交换 Person 1 和 Person 3 的位置，得到排列 $(3, 2, 1)$。
• 第 2 次操作：交换 Person 2 和 Person 3 的位置，得到排列 $(2, 3, 1)$。
• 第 3 次操作：交换 Person 1 和 Person 3 的位置，得到排列 $(2, 1, 3)$。

注意，在操作过程中，从前数第 $i$ 个人所穿的颜色不一定与 $c_i$ 一致。

10 4
2 7 1 8 2 8 1 8 2 8

132

数据范围

• $2 \leq N \leq 200000$
• $1 \leq K \leq 10^9$
• $1 \leq c_i \leq N$
• 输入中的所有值都是整数。