考虑以下实验。您有一副 $$$m$$$ 牌,并且只有一张牌是小丑牌。 $$$n$$$ 次,你执行以下操作:洗牌,取出牌堆最上面的牌,查看它并将其放回牌堆中。
设 $$$x$$$ 为您在本实验中将小丑从牌堆中取出的次数。假设每次洗牌时,所有 $$$m!$$$ 可能的牌排列都是等概率的,$$$x^k$$$ 的期望值是多少?打印答案对 $$$998244353$$$ 取模。
输入
唯一的一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m < 998244353$$$, $$$1 \le k \le 5000$$$)。
输出
打印一个整数 - $$$x^k$$$ 的期望值,以 $$$998244353$$$ 为模(答案始终可以表示为不可约分数 $$$\frac{a}{b}$$$,其中 $$$b \mod 998244353 \ne 0$$$;你必须打印 $$$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