题目描述
你发现了一个 $n \times m$ 的矩阵，矩阵中每个数字都在 $[1,k]$ 之间。很快，你发现了一个性质——考虑所有从左上角到右下角，每次只能向右或向下走出的路径，如果把每条路径经过格子上的数字依次写下来形成一个字符串，这些字符串两两互不相同。你认为这种矩阵应该被称为合法矩阵。
比如一个 $2 \times 2$ 的矩阵：
1 2
3 4所有的路径对应的字符串有：124,134 两种。这两种字符串互不相同，因此这个矩阵是一个合法的矩阵。
给定 $n,m,k$，求所有合法的矩阵。由于数量可能很大，输出答案 $\bmod\ 998244353$ 即可。
输入格式
第一行一个数字 $T$，表示数据组数。
接下来 $T$ 行每行三个正整数 $n,m,k$，意义如题面所述。
输出格式
共 $T$ 行，每行一个数表示合法矩阵的数量 $\bmod\ 998244353$ 的值。
样例输入
5
2 2 2
3 3 3
1000 1000 1000
100000 100000 100000
1000000000 1000000000 1000000000样例输出
8
3888
203329804
100484200
742247577样例解释
对于第一组数据，合法矩阵（共 $8$ 种，用逗号分隔）如下：
1 1 1 1 2 1 2 1 1 2 1 2 2 2 2 2
2 1, 2 2, 2 1, 2 2, 1 1, 1 2, 1 1, 1 2数据范围
对于 $100\%$ 的数据，$1 \le T \le 10^5,1 \le n,m,k \le 10^9$。
- $subtask1(10pts)$：$1 \le T \le 10,1 \le n,m,k \le 3$。
- $subtask2(20pts)$：$1 \le T \le 10,1 \le n,m,k \le 1000$。
- $subtask3(30pts)$：$1 \le T \le 10,1 \le n,m,k \le 10^5$。
- $subtask4(40pts)$：无特殊限制。
$by\ \text{djq_cpp}$
