题目描述

有 $N$ 个人，他们按从前向后的顺序排列，分别称为 Person $1$，Person $2$，$\\dots$，Person $N$。 Person $i$ 穿着颜色 $c_i$。

高桥重复以下操作 $K$ 次：随机选择两个人 $i$ 和 $j$ 并交换 Person $i$ 和 Person $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$

输出

打印答案。

示例输入 1

4 1
1 1 2 1

示例输出 1

3

下面是高桥的全部可能操作和每个操作后的人的排列方式：

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

示例输入 2

3 3
1 1 2

示例输出 2

1

下面是高桥的一种可能操作序列：

• 在第 $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$ 相同。

示例输入 3

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

示例输出 3

132