まず、次の補題を示します。

\((1,2\dots,N)\) を並べ替えた列 \(p = (p_1,p_2,\dots,p_N)\) について次の事実が成り立つ。

• \(i,j (i \neq j)\) を選んで \(p_i\) と \(p_j\) を swap したとき、 \(i \to p_i\) に辺が張られた \(N\) 頂点 \(N\) 辺のグラフに含まれるサイクル (大きさ \(1\) のサイクルも含む) の個数は \(1\) 増えるか \(1\) 減る。

(証明) サイクルに注目して考えると、あり得るのは次の \(2\) つのいずれかです。

• 長さ \(2\) 以上のサイクル \(a_1 \to a_2 \to \dots \to a_n \to a_1\) から異なる 2 点 \(a_i,a_j (i \lt j)\) を選んで \(p_{a_i}\) と \(p_{a_j}\) を swap する。
• 長さ \(1\) 以上のサイクル \(a_1 \to a_2 \to \dots \to a_n \to a_1,b_1 \to b_2 \to \dots b_n \to b_1\) から \(a_i,b_j\) を選んで\(p_{a_i}\) と \(p_{b_j}\) を swap する。

前者の場合、サイクルは \(a_1 \to a_2 \to \dots \to a_i \to a_{j+1} \to \dots \to a_n \to a_1\) と \(a_{i+1} \to a_{i+2} \to \dots \to a_{j} \to a_{i+1}\) の 2 つに分かれるのでサイクルは 1 個増えます。
後者の場合、サイクルは \(a_1 \to a_2 \to \dots \to a_i \to b_{j+1} \to \dots \to b_n \to b_1 \to \dots \to b_j \to a_{i+1} \to \dots \to a_n \to a_1\) と 1 つのサイクルになるのでサイクルは 1 個減ります。よって示されました。

ここから次の事実が従います。

\((1,2\dots,N)\) を並べ替えた列 \(p = (p_1,p_2,\dots,p_N)\) に関して、次の 2 つの命題は同値である。

(1) 列 \((1,2,\dots,N)\) に \(K\) 回の 2 点 swap を適用して \(p\) を作ることができる。
(2) \(i \to p_i\) に辺が張られた \(N\) 頂点 \(N\) 辺のグラフに含まれるサイクル (大きさ \(1\) のサイクルも含む) の個数を \(c\) としたとき、\(N - c \leq K\) かつ \(K \bmod 2 = (N-c) \bmod 2\) が成り立つ。

(1) \(\to\) (2) は偶奇に注目しつつ補題を用いれば確かめられます。
(2) \(\to\) (1) は、長さ \(2\) 以上のサイクルから 2 点を選び続ければ \(p=(p_1,p_2\dots,p_N)\) から \((1,2\dots,N)\) へ \(N-c\) 回の 2 点 swap でたどり着けることを利用すれば確かめられます。

• なお、この事実は偶置換・奇置換を利用して証明することもできます。

よって、\(c_{p_i} = c_i\) を満たす数列 \(p_1,p_2,\dots,p_N\) のうちサイクルの個数が \(1,2,\dots,N\) 個であるものを数え上げられれば、あとは上の事実を用いてこの問題を解くことができます。

dp テーブルを次のように置きます。

• \(dp_{n,k} :=\) \((1,\dots,n)\) の並べ替え \(q_1,q_2,\dots,q_n\) が \(c_{q_i} = c_i\) を満たしていて、かつ \(q_1,q_2,\dots,q_n\) のなすサイクルの個数が \(k\) 個である場合の数。

\(n\) 要素の並べ替えに \(n+1\) を追加して、サイクルの個数が \(k\) 個であるような並べ替えを作ることを考えます。追加する方法は 2 通りあります。

• \(n+1\) が新たに大きさ \(1\) のサイクルをなす場合は、それ以外のサイクルは \(k-1\) 個である必要があるので \(dp_{n,k-1}\) 通りである。
• すでに存在するサイクルに挿入する場合は、色が同じである \(x\) の後ろに挿入することになるので \(dp_{n,k} \times\) (\(c_1,c_2,\dots,c_n\) のうち \(c_{n+1}\) と一致するものの個数) 通りである。

よって次のような漸化式が立ちます。(\(\lbrace x \mid p \rbrace\) は条件 \(p\) を満たす \(x\) からなる集合、\(\#\) は集合のサイズを表す記号という意味で使っています。)

\[dp_{n+1,k} = dp_{n,k-1} + dp_{n,k} \times \#\lbrace i \mid 1 \leq i \leq n, c_i = c_{n+1}\rbrace\]

以上の DP を愚直に実装すると \(\mathrm{O}(N^2)\) になりますが、DP の遷移が多項式の積として表現できるのを利用すると、畳み込みとマージテクを組み合わせて \(\mathrm{O}(N \log^2 N)\) で計算することができます。

ちなみにこの問題は第 1 種スターリング数と同様の DP を取り上げたものになっています。特に \(c_i\) がすべて一致する場合は答えは第 \(1\) 種スターリング数を \(2\) 個飛ばしに足し合わせたものになります。

C++ による実装例は次の通りです。

#include <iostream>
#include <vector>
using namespace std;
#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> cnt(N + 1);
  vector<vector<mint>> Pi;
  for (int i = 0, x; i < N; i++) {
    cin >> x, Pi.push_back({cnt[x], 1}), cnt[x]++;
  }

  while (Pi.size() >= 2u) {
    vector<vector<mint>> nxt;
    for (int i = 0; i + 1 < (int)Pi.size(); i += 2) {
      nxt.push_back(atcoder::convolution(Pi[i], Pi[i + 1]));
    }
    if (Pi.size() % 2) nxt.push_back(Pi.back());
    swap(Pi, nxt);
  }
  auto f = Pi.back();

  mint ans = 0;
  for (int c = 0; c < (int)f.size(); c++) {
    if (N - c <= K and K % 2 == (N - c) % 2) ans += f[c];
  }
  cout << ans.val() << "\n";
}