CF1716F.Bags with Balls

There are $n$ bags, each bag contains $m$ balls with numbers from $1$ to $m$. For every $i \in [1, m]$, there is exactly one ball with number $i$ in each bag.

You have to take exactly one ball from each bag (all bags are different, so, for example, taking the ball $1$ from the first bag and the ball $2$ from the second bag is not the same as taking the ball $2$ from the first bag and the ball $1$ from the second bag). After that, you calculate the number of balls with odd numbers among the ones you have taken. Let the number of these balls be $F$.

Your task is to calculate the sum of $F^k$ over all possible ways to take $n$ balls, one from each bag.

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

你需要从每个袋子中恰好取出一个球（所有袋子互不相同，因此例如：从第一个袋子取编号为 $1$ 的球、从第二个袋子取编号为 $2$ 的球，与从第一个袋子取编号为 $2$ 的球、从第二个袋子取编号为 $1$ 的球，被视为两种不同的取法）。取出 $n$ 个球后，统计其中编号为奇数的球的个数，记该个数为 $F$。

你的任务是：对所有可能的取球方式（即从每个袋子各取一球的所有组合），求出对应的 $F^k$ 的总和。

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Each test case consists of one line containing three integers $n$, $m$ and $k$ ($1 \le n, m \le 998244352$; $1 \le k \le 2000$).

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

每个测试用例由一行组成，包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 998244352$；$1 \le k \le 2000$）。

For each test case, print one integer — the sum of $F^k$ over all possible ways to take $n$ balls, one from each bag. Since it can be huge, print it modulo $998244353$.

对于每个测试用例，输出一个整数——即对所有从每个袋子中各取一个球的可能方式，计算 $F^k$ 的总和。由于结果可能非常大，请对 $998244353$ 取模后输出。