注意

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T679600

题目描述

小明有一张被分成 $n$ 行 $m$ 列的地形图，第 $i$ 行第 $j$ 列位置被标记为 $(i,j)$，这个位置的海拔为 $h_{i,j}$。

称一个位置 $(i,j)$ 为「山峰」，当且仅当它的海拔严格高于所有与它相邻（与它有公共边）的格子的海拔。

设定义 $f(i,j,k)$ 等于「若将 $h_{i,j}$ 修改为 $k$，地形图中「山峰」的数量」。

计算：

$$\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{A} f(i,j,k)$$

答案对 $\bm{998244353}$ 取模。

输入格式

第一行三个正整数 $n, m, A$。

下面一个 $n \times m$ 的正整数矩阵 $\{h_{n, m}\}$。

输出格式

一行一个非负整数表示答案。

样例

2 2 2
1 2
2 1

10

1 1 10000
1

10000

样例 1 解释

按照题目方式修改地形图，得到 $8$ 张地形图：

$$\def\arraystretch{1.5} \begin{array}{|cc|cc|cc|cc|} \hline 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 \\ 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ \hline 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 1 & 1 & 2 & 1 & 2 & 1 & 2 & 2 \\ \hline \end{array}$$

得到它们对应的 $f$ 值为：

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline f(1,1,1)=2 & f(1,1,2)=0 & f(1,2,1)=1 & f(1,2,2)=2 \\ \hline f(2,1,1)=1 & f(2,1,2)=2 & f(2,2,1)=2 & f(2,2,2)=0 \\ \hline \end{array}$$

$(2+0+1+2+1+2+2+0) \bmod 998244353=10$，输出 $10$。

样例 2 解释

发现对于任意正整数 $x$，$f(1,1,x)=1$。

所以，显然答案为 $A$，输出 $10000$。

数据范围

对于 $10\%$ 的数据，$n,m \le 10$，$nmA \le 10^4$。

对于 $30\%$ 的数据，$nmA \le 5 \times 10^7$。

对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$1 \le A \le 10^9$，$1 \le h_{i,j} \le 10^9$。

注意，不保证 $\bm{h_{i, j} \le A}$。