配点 : $600$ 点

問題文

縦 $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$ で割った余りを求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

出力

列対 $(A,B)$ としてありうる相異なるものの個数を $998244353$ で割った余りを出力せよ。

2 2 2

7

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

1 1 100

100

31415 92653 58979

469486242