装球的袋子

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有 $n$ 个互不相同的袋子，每个袋子中恰好有 $m$ 个球，编号为 $1,2,\ldots,m$。

从每个袋子中各取一个球。设取出的奇数编号球数量为 $F$。请计算所有 $m^n$ 种取法的 $F^k$ 之和，并对 $998244353$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例一行三个整数 $n,m,k$。

输出格式

对每个测试用例输出一行一个整数，表示所求和对 $998244353$ 取模的结果。

样例输入

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

样例输出

1028
1
3
729229716
652219904

数据范围

对所有数据，$1\le t\le5000$，$1\le n,m\le998244352$，$1\le k\le2000$。