Problem Description

There are $m$ cards, among which one is the王牌 (Joker). These cards are shuffled uniformly randomly $n$ times. Let $x$ be the number of times the first card is the Joker. Find the expected value of $x^k$.

The answer should be modulo $998244353$.

Input Format

A single line containing three positive integers $n, m, k$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

1234 2345 3456

Sample Output #1

398700213

Sample Input #2

998244352 1337 5000

Sample Output #2

326459680

Sample Input #3

233333333 114514 9982443

Sample Output #3

825888958

Notes

Data Range

• For $20\%$ of the data, $1 \le k \le 5000$.
• For $40\%$ of the data, $1 \le k \le 10^5$.
• For $100\%$ of the data, $1 \le k \le 10^7$ and $1 \le n, m \le 998244352$.

见题面 Input 部分

见题面 Output 部分