C - Grid Coloring 3 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

H 行 W 列のグリッドがあり、はじめすべてのマスは無色です。

このグリッドに対して、下記の手順を好きな回数だけ繰り返します。

  • まず、1 以上 C 以下の整数 i と、マス 1 個を選ぶ。
  • その後、選んだマスおよび、選んだマスと同じ行にあるすべてのマス、選んだマスと同じ列にあるすべてのマスの、合計 (H+W-1) マスを色 i で塗る（すでに色が塗られている場合は、その色を色 i で上書きする）。

上記の手順を繰り返して得られる、すべてのマスに色が塗られている グリッドとしてありえるものの個数を 998244353 で割った余りを出力してください。

制約

  • 1 \leq H, W \leq 400
  • 1 \leq C \leq 10^9
  • 入力はすべて整数

入力

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

H W C

出力

答えを出力せよ。

入力例 1

2 3 2

出力例 1

26

以下、上から i 行目、左から j 行目のマスを (i, j) で表します。 また、無色のマス、色 1 で塗られたマス、色 2 で塗られたマスをそれぞれ . 、1 、2 で表します。 入力例１に対応する初期状態のグリッドから、まず色 2 とマス (2, 2) を選択して操作を行うと、グリッドの状態は

.2.
222

となります。 続けて、色 1 とマス (1, 1) を選択して操作を行うと、グリッドの状態は

111
122

となります。このグリッドはすべてのマスに色が塗られているため、 問題文中の「上記の手順を繰り返して得られる、すべてのマスに色が塗られているグリッド」に該当します。 さらに、色 1 とマス (1, 3) を選択して操作を行うと、グリッドの状態は

111
121

となります。このグリッドも問題文中の「上記の手順を繰り返して得られる、すべてのマスに色が塗られているグリッド」に該当します。

入力例 2

3 2 1

出力例 2

1

入力例 3

229 327 763027379

出力例 3

547014653

Score : 1000 points

Problem Statement

There is a grid of H rows and W columns. Initially, all cells are uncolored.

You can repeat the following procedure any number of times:

  • Choose an integer i between 1 and C, inclusive, and choose exactly one cell in the grid.
  • Then, color that chosen cell, as well as all cells in the same row as the chosen cell and all cells in the same column as the chosen cell (a total of (H+W-1) cells), with color i. (If any cell is already colored, its color is overwritten with color i.)

Print the number, modulo 998244353, of different grids in which every cell is colored that can be obtained by repeating the procedure above.

Constraints

  • 1 \leq H, W \leq 400
  • 1 \leq C \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

H W C

Output

Print the answer.

Sample Input 1

2 3 2

Sample Output 1

26

Below, let (i, j) denote the cell at the i-th row from the top and the j-th column from the left. Also, let ., 1, 2 denote an uncolored cell, a cell colored with color 1, a cell colored with color 2, respectively.

From the initial grid in Sample Input 1, if you first choose color 2 and cell (2, 2), the grid becomes:

.2.
222

Then, if you choose color 1 and cell (1, 1), the grid becomes:

111
122

All cells are colored in this grid, so it satisfies the condition in the problem statement. Furthermore, if you then choose color 1 and cell (1, 3), the grid becomes:

111
121

All cells are again colored in this grid, satisfying the condition in the problem statement.

Sample Input 2

3 2 1

Sample Output 2

1

Sample Input 3

229 327 763027379

Sample Output 3

547014653