题目描述

在一个纵向 $N$ 格、横向 $M$ 格的网格中，每个格子内填写一个 $1$ 到 $K$ 之间的整数。定义序列 $A,B$ 如下：

• 对于 $i=1,\dots,N$，$A_i$ 表示第 $i$ 行所有格子中填写的整数的最小值。
• 对于 $j=1,\dots,M$，$B_j$ 表示第 $j$ 列所有格子中填写的整数的最大值。

给定 $N,M,K$，请计算所有可能的不同序列对 $(A,B)$ 的数量，并对 $998244353$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$ $K$

输出格式

输出所有可能的不同序列对 $(A,B)$ 的数量，对 $998244353$ 取模。

样例 1

输入

2 2 2

输出

7

样例 2

输入

1 1 100

输出

100

样例 3

输入

31415 92653 58979

输出

469486242

说明/提示

限制条件

• $1 \leq N, M, K \leq 2 \times 10^5$
• 输入均为整数

样例解释 1

所有可能的 $(A_1,A_2,B_1,B_2)$ 为：$(1,1,1,1)$、$(1,1,1,2)$、$(1,1,2,1)$、$(1,1,2,2)$、$(1,2,2,2)$、$(2,1,2,2)$、$(2,2,2,2)$，共 $7$ 种情况。

由 ChatGPT 4.1 翻译