Problem Description

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 Format

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

Output Format

Output one integer, the answer modulo $998244353$.

3 4 0

21

Hint

This problem uses bundled testdata.

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