CF1716F Bags with Balls

这里有 $n$ 个袋子，每个袋子里面有 $m$ 个带有从 $1 \sim m$ 标记的球。对于每一个 $1 \leq i \leq m$ 来说，每个袋子中都一定存在一个带有 $i$ 标记的球。 你需要在每个袋子中取出一个球（所有的袋子都是不同的，比如在 $1$ 号袋子取 $2$ 号球并且从 $2$ 号袋子里取 $1$ 号球与从 $1$ 号袋子取 $1$ 号球并且从 $2$ 号袋子取 $2$ 号球是不同的两种方案）然后计算出你取出的标号是奇数的球的数量，记这个数量为 $F$ 。 你的任务是计算所有可能的取球方案的 $F^k$ 之和。

第一行包含一个整数 $t$（$ 1 \leq t \leq 5000$）表示测试用例的数量。 每组第一行输入三个整数 $n$ , $m$ 和 $k$（$1 \leq n, m \leq 998244352$；$1 \leq k \leq 2000$）。

每组测试输出一个整数：$F^k$（意义见题面）。由于它可能会很大，请将它模 $998244353$ 后输出。