[ABC247Ex] Rearranging Problem

给定值域为 $[1, n]$ 的序列 $c_i$，进行 $k$ 次操作：每次选定任意 $i\not= j$ 然后交换 $c_i$ 和 $c_j$。问会形成多少种不同的下标序列，满足没交换之前和所有操作完成之后序列 $c_i$ 不变。

[problemUrl]: https://atcoder.jp/contests/abc247/tasks/abc247_h 人 $ 1 $, 人 $ 2 $, $ \dots $, 人 $ N $ の $ N $ 人の人がいて、前から $ (1,2,\dots,N) $ の順に一列に並んでいます。人 $ i $ は色 $ c_i $ の服を着ています。 高橋君は任意の $ 2 $ 人 $ i,j $ を選んで人 $ i $ と人 $ j $ の位置を入れ替える操作を $ K $ 回繰り返しました。 $ K $ 回の操作を終了した時点で、$ 1\ \leq\ i\ \leq\ N $ を満たすすべての整数 $ i $ に対して、前から $ i $ 番目の人が着ている服の色は $ c_i $ と一致しました。 $ K $ 回の操作を終了した後にあり得る人の並び方は何通りありますか？ 答えを $ 998244353 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ c_1 $ $ c_2 $ $ \dots $ $ c_N $

答えを出力せよ。

4 1
1 1 2 1

3

3 3
1 1 2

1

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 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 高橋君の操作、および操作後の列としてあり得るものをすべて挙げると次のようになります。 - 人 $ 1 $ と人 $ 2 $ の位置を入れ替える。操作後の並び方は $ (2,\ 1,\ 3,\ 4) $ となる。 - 人 $ 1 $ と人 $ 4 $ の位置を入れ替える。操作後の並び方は $ (4,\ 2,\ 3,\ 1) $ となる。 - 人 $ 2 $ と人 $ 4 $ の位置を入れ替える。操作後の並び方は $ (1,\ 4,\ 3,\ 2) $ となる。 ### Sample Explanation 2 あり得る高橋君の操作の例を 1 つ挙げると次のようになります。 - $ 1 $ 回目の操作で人 $ 1 $ と人 $ 3 $ の位置を入れ替える。操作後の並び方は $ (3,\ 2,\ 1) $ となる。 $ 2 $ 回目の操作で人 $ 2 $ と人 $ 3 $ の位置を入れ替える。操作後の並び方は $ (2,\ 3,\ 1) $ となる。 $ 3 $ 回目の操作で人 $ 1 $ と人 $ 3 $ の位置を入れ替える。操作後の並び方は $ (2,\ 1,\ 3) $ となる。 操作の途中においては、前から $ i $ 番目の人の服の色が $ c_i $ と必ずしも一致しなくてもよいのに注意してください。