← 返回题目列表

Codeforces · 1278/F

F. 卡

中文机器翻译题面 查看原题

考虑以下实验。您有一副 $$$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