筱踅栖生态保护区是一个n×mn\times mn×m的方格图,第iii行第jjj列的方格记为(i,j)(i,j)(i,j),第coli,jcol_{i,j}coli,j种生物栖息于其中。现在,学生们想要考察筱踅栖的生物,在考察期间,他们希望收集筱踅栖生物的标本。
学生们初始在(1,1)(1,1)(1,1),而终点在(n,m)(n,m)(n,m)。每天,学生可以向右或者向下移动一个方格,但不能移出这个方格图。如果学生们到达一个方格,则可以采集方格中的生物标本,包括初始时(1,1)(1,1)(1,1)的生物标本。
学生们想知道在路途中每种生物标本至少采集一次的路径方案数。答案对998,244,353998,244,353998,244,353取模。
第一行三个整数n,m,qn,m,qn,m,q,为方格行数,列数和种类数。
接下来nnn行,每行mmm个整数coli,jcol_{i,j}coli,j,为每个方格的生物种类。
仅一个整数,为答案。
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
210
3 3 3 1 2 2 1 3 1 1 1 1
2
1≤n,m≤1001 \leq n,m \leq 1001≤n,m≤100
1≤q≤101 \leq q \leq 101≤q≤10
对于样例一,如下图所示,任意一条从(1,1)(1,1)(1,1)只向下或向右的路径均是合法路径。
对于样例二,合法路径如下:
(1,1),(1,2),(2,2),(3,2),(3,3) (1,1),(1,2),(2,2),(2,3),(3,3)