← 返回题目列表

Codeforces · 2048/G

G. 凯文和矩阵

中文机器翻译题面 查看原题

Kevin 已被送往圣心医院,该医院包含所有 $$$ n \times m $$$ 矩阵,其整数值在 $$$ [1,v] $$$ 范围内。

现在,Kevin 想与一些矩阵交友,但当且仅当满足以下条件时,他愿意与矩阵 $$$ a $$$ 交友:

$$$$$$ \min_{1\le i\le n}\left(\max_{1\le j\le m}a_{i,j}\right)\le\max_{1\le j\le m}\left(\min_{1\le i\le n}a_{i,j}\right)。 $$$$$$

请数一下圣心医院里有多少个矩阵可以和凯文成为好友。

由于Kevin非常友好,可能有很多矩阵满足这个条件。因此,只需输出对 $$$998\,244\,353$$$ 取模的结果即可。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$ t $$$ ($$$ 1 \le t \le 8\cdot 10^3 $$$)。

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$m$$$、$$$v$$$ ($$$ 1 \le n, v, n \cdot v \leq 10^6$$$, $$$1 \le m \le 10^9 $$$)。

保证所有测试用例的 $$$ n \cdot v $$$ 之和不超过 $$$ 10^6 $$$。

输出

对于每个测试用例,输出一个整数——可以与 Kevin 模 $$$998\,244\,353$$$ 为友元的矩阵数量。

示例

输入 #1

3
2 2 2
2 3 4
11 45 14

输出 #1

14
2824
883799966

注意

第一个测试用例中,除了矩阵 $$$ a=\begin{bmatrix}1&2\\2&1\end{bmatrix} $$$ 和 $$$ a=\begin{bmatrix}2&1\\1&2\end{bmatrix} $$$ 不满足条件外,其余 $$$ 2^{2 \cdot 2} - 2 = 14 $$$矩阵都可以和凯文做朋友。