Description

There are $m$ cards, and one of them is a joker. Shuffle these cards uniformly at random $n$ times. Let $x$ be the number of times the first card is the joker. Find the expected value of $x^k$.

Take the answer modulo $998244353$.

Input Format

One line with three positive integers $n, m, k$.

Output Format

Output one integer in one line, which is the answer.

1234 2345 3456

398700213

998244352 1337 5000

326459680

233333333 114514 9982443

825888958

Hint

Constraints
For $20\%$ of the testdata, $1 \le k \le 5000$;
For $40\%$ of the testdata, $1 \le k \le 10^5$;
For $100\%$ of the testdata, $1 \le k \le 10^7$, $1 \le n, m \le 998244352$.

Solution: iostream
Data: NaCly_Fish

Translated by ChatGPT 5