← 返回题目列表

Codeforces · 1716/F

F. 带球的袋子

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

有$$$n$$$袋,每个袋包含$$$m$$$个球,号码从$$$1$$$到$$$m$$$。对于 [1, m]$$$ 中的每个 $$$i,每个袋子中恰好有一个编号为 $$$i$$$ 的球。

您必须从每个袋子中取出一个球(所有袋子都不同,因此,例如,从第一个袋子中取出球 $$$1$$$ 并从第二个袋子中取出球 $$$2$$$ 与从第一个袋子中取出球 $$$2$$$ 并从第二个袋子中取出球 $$$1$$$ 是不同的)。之后,您计算出您所拿走的球中奇数个球的数量。设这些球的数量为$$$F$$$。

你的任务是计算从每袋中取出 $$$n$$$ 个球的所有可能方式的 $$$F^k$$$ 总和。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 998244352$$$; $$$1 \le k \le 2000$$$)。

输出

对于每个测试用例,打印一个整数 - $$$F^k$$$ 的所有可能方式的总和 $$$n$$$ 球,每个袋子中一个。因为它可能很大,所以打印它对 $$$998244353$$$ 取模。

示例

输入 #1

5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000

输出 #1

1028
1
3
729229716
652219904