有$$$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