Training, Round 3

Ashley is training for another programming contest on Brandon's Online Judge.

Ashley has $k$ weeks left to train for her next programming contest. Her coach, Tom, is very busy and no longer picks specific problems for Ashley. At the start of every week, Tom picks $p$ distinct problems from the bank of $n$ problems on Brandon's Online Judge, independently and uniformly at random, and assigns them to Ashley. Tom generates a total of $k$ sets of problems in this manner.

Ashley solves every problem that Tom picks. However, she gets annoyed if two different weeks share at least one problem, because she wants to solve unique problems.

Compute the probability that Ashley becomes annoyed.

The input is one line with three integers $n$ $(1 \le n \le 10^7)$, $k$ $(1 \le k \le 10^7)$, and $p$ $(1 \le p \le n)$.

Let $p$ be the probability that Ashley becomes annoyed. It can be shown that $p$ can be written as a rational number $\frac{x}{y}$ with $\gcd(x, y) = 1$ and $y \not\equiv 0 \pmod{998244353}$. Define $r$ to be the unique integer in $[0, 998244353)$ such that $r \cdot y \equiv x \pmod{998244353}$. Output $r$.

Under the given constraints, $r$ is guaranteed to exist and be unique.

In the first sample, the probability that Ashley becomes annoyed is $\frac{7}{9}$. Since $110916040 \cdot 9 \equiv 7 \pmod {998244353}$, the output is 110916040.

In the second sample, Ashley always becomes annoyed. Since $1 \cdot 1 \equiv 1 \pmod {998244353}$, the output is 1.

In the third sample, Ashley never becomes annoyed. Since $0 \cdot 1 \equiv 0 \pmod {998244353}$, the output is 0.