P17285 "IXOI R2" I Won’t Explain, But You Have "Yuyu Steamed"

Given $n, m, k$, we call a sequence $a$ of length $n$ good if and only if: - $\sum_{i=1}^n a_i = m$. - $\sum_{i=1}^n (a_i \bmod 2) = k$. We generate $a$ in a special way: initially set $a_p \leftarrow 0$ for all $p$. Then perform $m$ operations. In each operation, choose $p \in [1, n]$ uniformly at random, and then set $a_p \leftarrow a_p + 1$. Let $P$ be the probability that after $m$ operations, the generated sequence $a$ is good. Compute $(P \cdot n^m) \bmod 998244353$.

Input one line with three integers $n, m, k$.

Output one integer, the answer modulo $998244353$.

**This problem uses bundled testdata.** | Subtask | Constraints | Score | | :-----: | :---------: | :---: | | $1$ | $n, m \le 10$ | $10$ | | $2$ | $m \le 5000$ | $20$ | | $3$ | $k = m$ | $20$ | | $4$ | $n \le 5\times 10^5$ | $25$ | | $5$ | No special restrictions. | $25$ | For all testdata, it is guaranteed that: $0 \le n, m, k \le 3\times 10^7$, and $n \ge 1$. Translated by ChatGPT 5