#1349. 筱踅栖

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Rhodoks

题目描述

筱踅栖生态保护区是一个n×mn\times m的方格图,第ii行第jj列的方格记为(i,j)(i,j),第coli,jcol_{i,j}种生物栖息于其中。现在,学生们想要考察筱踅栖的生物,在考察期间,他们希望收集筱踅栖生物的标本。

学生们初始在(1,1)(1,1),而终点在(n,m)(n,m)。每天,学生可以向右或者向下移动一个方格,但不能移出这个方格图。如果学生们到达一个方格,则可以采集方格中的生物标本,包括初始时(1,1)(1,1)的生物标本。

学生们想知道在路途中每种生物标本至少采集一次的路径方案数。答案对998,244,353998,244,353取模。

输入格式

第一行三个整数n,m,qn,m,q,为方格行数,列数和种类数。

接下来nn行,每行mm个整数coli,jcol_{i,j},为每个方格的生物种类。

输出格式

仅一个整数,为答案。

样例

样例输入1

5 7 3
1 2 1 2 1 3 3
1 2 1 2 1 3 3
2 1 2 1 2 3 3
2 1 2 1 2 3 3
3 3 3 3 3 3 3

样例输出1

210

样例输入2

3 3 3
1 2 2
1 3 1
1 1 1

样例输出2

2

数据范围与提示

1n,m1001 \leq n,m \leq 100

1q101 \leq q \leq 10

对于样例一,如下图所示,任意一条从(1,1)(1,1)只向下或向右的路径均是合法路径。

对于样例二,合法路径如下:

(1,1),(1,2),(2,2),(3,2),(3,3)
(1,1),(1,2),(2,2),(2,3),(3,3)