CF1716F Bags with Balls

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

第一行包含一个整数 $ t $ ( $ 1 \le t \le 5000 $ ) — 测试组数的数量 每组第一行输入三个整数 $ n $ , $ m $ 和 $ k $ ( $ 1 \le n, m \le 998244352 $ ; $ 1 \le k \le 2000 $ ).

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