/ 
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
正整数 H,W,M が与えられます.
各要素が 1 以上 M 以下の整数である H 行 W 列の行列 A であって，次の条件を満たすものの個数を 998244353 で割ったあまりを求めてください.
\[ \min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j} \]
ここで A_{i,j} は行列 A の i 行目 j 列目の要素を表します.
制約
- 1 \le H,W \le 200
- 1 \le M \le 10^8
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる.
H W M
出力
答えを出力せよ.
入力例 1
2 2 3
出力例 1
67
たとえば，A=\begin{pmatrix} 1 & 2\\ 2 & 3\end{pmatrix} は条件を満たします.
- \displaystyle\min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}=2 が成り立ちます.
一方，A=\begin{pmatrix} 1 & 3\\ 3 & 2\end{pmatrix} は条件を満たしません.
- \displaystyle\min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=3,\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}=2 です.
条件を満たす A は 67 通りあります.
入力例 2
99 82 44353
出力例 2
213254234
Score : 900 points
Problem Statement
You are given positive integers H, W, and M.
Find the number, modulo 998244353, of H\times W matrices A, each of whose elements is an integer between 1 and M (inclusive), satisfying the following condition.
\[ \min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j} \]
Here, A_{i,j} denotes the element at the i-th row and j-th column of matrix A.
Constraints
- 1 \le H,W \le 200
- 1 \le M \le 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W M
Output
Output the answer.
Sample Input 1
2 2 3
Sample Output 1
67
For example, A=\begin{pmatrix} 1 & 2\\ 2 & 3\end{pmatrix} satisfies the condition.
- \displaystyle\min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}=2 holds.
On the other hand, A=\begin{pmatrix} 1 & 3\\ 3 & 2\end{pmatrix} does not satisfy the condition.
- \displaystyle\min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=3,\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}=2.
There are 67 matrices A satisfying the condition.
Sample Input 2
99 82 44353
Sample Output 2
213254234