题目描述

縦 $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$ で割った余りを出力せよ。

题目大意

在一个 $N$ 行 $M$ 列的方格 $G$ 中，每一个方格中可以放置 $1 \sim K$ 中的任何一个数。

我们定义序列 $A,B$ 定义如下：

现在给定 $N,M,K$。问共有多少种不同的序列对 $(A,B)$，答案对 $998244353$ 取模。

2 2 2

7

1 1 100

100

31415 92653 58979

469486242

提示

制約

• $1\ \leq\ N,M,K\ \leq\ 2\times\ 10^5$
• 入力はすべて整数である

Sample Explanation 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$ 通りです。