We first prove the following lemma.

For any sequence \(p = (p_1,p_2,\dots,p_N)\) that is a permutation of \((1,2\dots,N)\), the following fact holds:

• By choosing \(i\) and \(j\) (\(i \neq j\)) and swapping \(p_i\) and \(p_j\), in the graph with \(N\) vertices and \(N\) edges where there is an edge \(i \to p_i\), the number of cycles (including a cycle of size \(1\)) increases or decreases by \(1\).

(Proof) Focusing on the cycle, there are only the following two possibilities:

• Choosing two different points \(a_i\) and \(a_j\) (\(i \lt j\)) from a cycle \(a_1 \to a_2 \to \dots \to a_n \to a_1\) of length at least \(2\), and swapping \(p_{a_i}\) and \(p_{a_j}\).
• Choosing points \(a_i\) and \(b_j\) from cycles with lengths at least \(1\), \(a_1 \to a_2 \to \dots \to a_n \to a_1\) and \(b_1 \to b_2 \to \dots b_n \to b_1\), respectively, and swapping \(p_{a_i}\) and \(p_{b_j}\).

In the former case, the cycle splits off to \(a_1 \to a_2 \to \dots \to a_i \to a_{j+1} \to \dots \to a_n \to a_1\) and \(a_{i+1} \to a_{i+2} \to \dots \to a_{j} \to a_{i+1}\), so the number of cycles increases by \(1\).
In the latter case, the cycles are merged into a single cycle \(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\), so the number of cycle decreases by \(1\). Therefore, it has been shown.

Then the following fact follows.

For any sequence \(p = (p_1,p_2,\dots,p_N)\) that is a permutation of \((1,2\dots,N)\), the following two conjectures are equivalent:

• It is possible to apply two-point swap \(K\) times to a sequence \((1,2,\dots,N)\).
• Let \(c\) be the number of cycles (including a cycle of size \(1\)) in the graph with \(N\) vertices and \(N\) edges where there is an edge \(i \to p_i\), then \(N - c \leq K\) and \(K \bmod 2 = (N-c) \bmod 2\) hold.

This can be justified by using the lemma while focusing on the parity.

• This fact can alternatively be proved using the properties of odd and even inversions.

Therefore, the problem can be solved using the fact above if we can count the number of sequences \(p_1,p_2,\dots,p_N\) satisfying \(c_{p_i} = c_i\) such that the number of cycles is \(1,2,\dots,N\).

Let us define the DP (Dynamic Programming) table as follows.

• \(dp_{n,k} :=\) the number of permutations \(q_1,q_2,\dots,q_n\) of \((1,\dots,n)\) satisfying \(c_{q_i} = c_i\) such that the number of cycles formed by \(q_1,q_2,\dots,q_n\) is \(k\).

Consider making a permutation with \(k\) cycles by adding \(n+1\) to a permutation of \(n\) elements. There are two ways to do so.

• If \(n+1\) forms a new cycle of size \(1\), then there should originally be \(k-1\) cycles, so there are \(dp_{n,k-1}\) ways.
• If it is inserted to an already existing cycle, then it should be inserted right after \(x\) with the same color, so there are \(dp_{n,k} \times\) (the number of elements in \(c_1,c_2,\dots,c_n\) that is equal to \(c_{n+1}\)).

Therefore, we have the following recurrence relation. (\(\lbrace x \mid p \rbrace\) denotes a set consisting of \(x\) satisfying \(p\); \(\#\) denotes the size of the set.)

\[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\]

A naive implementation of the DP above costs \(\mathrm{O}(N^2)\), but can be sped up to \(\mathrm{O}(N \log^2 N)\) using convolutions and merging technique, by using the property that the transitions DP can be expressed as a product of polynomials.

By the way, this problem treats the same DP as that of computing the Stirling number of first kind. Especially, when \(c_i\) are all equal, the answer is a sum of the Stirling number of first kind added up every other one.

The following is a sample code in 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";
}