← 返回题目列表

AtCoder · arc193_c

C. 网格着色 3

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有一个网格 H 行和 W 列。最初,所有细胞都是无色的。

您可以重复以下过程任意次:

  • 选择一个整数 i 之间 1 和 C,包含在内,并在网格中仅选择一个单元格。
  • 然后,为所选单元格以及与所选单元格同一行中的所有单元格以及与所选单元格同一列中的所有单元格着色(总共 (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。

从示例输入 1 中的初始网格开始,如果您首先选择颜色 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