分数: 600 点
问题陈述
有一个网格 H 水平行和 W 垂直列,其中每个方格包含一个数字 1 和 9。 对于每对整数 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W,写在方块上的数字 i从顶部数第行和 j左起第 列是 c_{i, j}.
使用这个网格,高桥和青木将一起玩。 首先,高桥选择一个正方形,并在上面放一块棋子。 然后,两人将重复以下过程,1.到4., N 次。
- Takahashi 执行以下两个操作之一。
- 将棋子移动到另一个方格, 共享一行 与该块所在的正方形。
- 什么都不做。
- 高桥在黑板上写下棋子所在方块上写的数字。
- Aoki 执行以下两个操作之一。
- 将棋子移动到另一个方格, 分享专栏 与该块所在的正方形。
- 什么都不做。
- 青木在黑板上写下棋子所在方块上写的数字。
之后,将会有 2N 数字写在黑板上。让 d_1, d_2, \ldots, d_{2N} 是那些数字,按照它们的书写顺序排列。 这两个男孩将串联起来 2N 数字按此顺序进行 2N- 数字整数 X := d_1d_2\ldots d_{2N}.
求模数 998244353,不同的整数 X 可以成为。
约束
- 2 \leq H, W \leq 10
- 1 \leq N \leq 300
- 1 \leq c_{i, j} \leq 9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W N
c_{1, 1}c_{1, 2}\cdotsc_{1, W}
c_{2, 1}c_{2, 2}\cdotsc_{2, W}
\vdots
c_{H, 1}c_{H, 2}\cdotsc_{H, W}
输出
打印数字,模数 998244353,不同的整数 X 可以成为。
示例输入 1
2 2 1 31 41
示例输出 1
5
以下是一种可能的情况。
- 首先,高桥把这件作品穿上 (1, 2).
- 高桥将棋子从 (1, 2) to (1, 1),然后写入数字 3 写于 (1, 1).
- 青木将棋子从 (1, 1) to (2, 1),然后写入数字 4 写于 (2, 1).
在这种情况下,我们有 X = 34.
下面是另一种可能的情况。
- 首先,高桥把这件作品穿上 (2, 2).
- 高桥继续演奏 (2, 2),然后写入数字 1 写于 (2, 2).
- 青木将棋子从 (2, 2) to (1, 2),然后写入数字 1 写于 (1, 2).
在这种情况下,我们有 X = 11。
除了这些之外, X 也可以变成 33, 44,或 43,但仅此而已。
也就是说,有五个整数 X 可以变成,所以我们打印 5.
示例输入 2
2 3 4 777 777
示例输出 2
1
X 只能成为 77777777.
示例输入 3
10 10 300 3181534389 4347471911 4997373645 5984584273 1917179465 3644463294 1234548423 6826453721 5892467783 1211598363
示例输出 3
685516949
一定要找到计数模数 998244353.