当前没有测试数据。

Ex - 重新排列问题

得分：600分

问题陈述

有$N$个人，依次排列在一排中，从前到后的顺序是$(1,2,\dots,N)$。第$i$个人穿着颜色$c_i$。
Takahashi重复了以下操作$K$次：任意选择两个人$i$和$j$，交换第$i$个人和第$j$个人的位置。
在进行了$K$次操作后，从前面开始数的第$i$个人穿着的颜色与$c_i$相同，对于满足$1 \leq i \leq N$的所有整数$i$。
在$K$次操作之后，有多少种可能的人排列方式？以$998244353$为模求出结果。

约束

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

输入

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

$N$ $K$

$c_1$ $c_2$ $\dots$ $c_N$

输出

打印答案。

4 1
1 1 2 1

3

这里列出了所有可能的Takahashi操作及每次操作后人员排列的情况。

• 交换第一个人和第二个人的位置，得到排列$(2, 1, 3, 4)$。
• 交换第一个人和第四个人的位置，得到排列$(4, 2, 3, 1)$。
• 交换第二个人和第四个人的位置，得到排列$(1, 4, 3, 2)$。

3 3
1 1 2

1

这是Takahashi操作的一种可能序列的例子。

• 在第$1$次操作中，他交换了第一个人和第三个人的位置，得到排列$(3, 2, 1)$。
  在第$2$次操作中，他交换了第二个人和第三个人的位置，得到排列$(2, 3, 1)$。
  在第$3$次操作中，他交换了第一个人和第三个人的位置，得到排列$(2, 1, 3)$。

请注意，在操作序列中，从前面开始数的第$i$个人穿着的颜色不一定与$c_i$相同。

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

132

注：此处省略了过长的部分。