Cards

题意翻译

有 $m$ 张牌，其中一张是王牌。现在你执行 $n$ 次如下操作：洗牌后查看第一张牌是什么。 令 $x$ 为洗牌后第一张牌为王牌的次数，现在假设洗牌时 $m!$ 种牌的排列出现的概率均相等，求 $x^k$ 的期望值。

题目描述

Consider the following experiment. You have a deck of $ m $ cards, and exactly one card is a joker. $ n $ times, you do the following: shuffle the deck, take the top card of the deck, look at it and return it into the deck. Let $ x $ be the number of times you have taken the joker out of the deck during this experiment. Assuming that every time you shuffle the deck, all $ m! $ possible permutations of cards are equiprobable, what is the expected value of $ x^k $ ? Print the answer modulo $ 998244353 $ .

输入输出格式

输入格式

The only line contains three integers $ n $ , $ m $ and $ k $ ( $ 1 \le n, m < 998244353 $ , $ 1 \le k \le 5000 $ ).

输出格式

Print one integer — the expected value of $ x^k $ , taken modulo $ 998244353 $ (the answer can always be represented as an irreducible fraction $ \frac{a}{b} $ , where $ b \mod 998244353 \ne 0 $ ; you have to print $ a \cdot b^{-1} \mod 998244353 $ ).

输入输出样例

输入样例 #1

1 1 1

输出样例 #1

1

输入样例 #2

1 1 5000

输出样例 #2

1

输入样例 #3

2 2 2

输出样例 #3

499122178

输入样例 #4

998244352 1337 5000

输出样例 #4

326459680