/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 で割った余りを出力せよ。
入力例 1
2 2 2
出力例 1
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 通りです。
入力例 2
1 1 100
出力例 2
100
入力例 3
31415 92653 58979
出力例 3
469486242
Score : 600 points
Problem Statement
In a grid with N horizontal rows and M vertical columns of squares, we will write an integer between 1 and K (inclusive) on each square and define sequences A, B as follows:
- for each i=1,\dots, N, A_i is the minimum value written on a square in the i-th row;
- for each j=1,\dots, M, B_j is the maximum value written on a square in the j-th column.
Given N, M, K, find the number of different pairs of sequences that can be (A, B), modulo 998244353.
Constraints
- 1 \leq N,M,K \leq 2\times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the number of different pairs of sequences that can be (A, B), modulo 998244353.
Sample Input 1
2 2 2
Sample Output 1
7
(A_1,A_2,B_1,B_2) can be (1,1,1,1), (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,2,2,2), (2,1,2,2), or (2,2,2,2) - there are seven candidates.
Sample Input 2
1 1 100
Sample Output 2
100
Sample Input 3
31415 92653 58979
Sample Output 3
469486242