T720710 [CFCOI] 直方图

$\text{histogram.cpp},1 \text{ s},512 \text{ MiB}$

小明有一个长度为 $n$ 的整数数列 $a_1,a_2,\cdots,a_n$。任何一个数都在 $[1,V]$ 之间。 小明定义： 1. 由数列 $A$ 生成的点集 $S=\{(i,j) \mid 1 \le i \le n \land j \le a_i \land j \in \mathbb N^*\}$。 2. 定义点集 $P \subseteq S$ 是连通的，当且仅当存在 $(x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)$ 满足： + $\forall 1 \le i \le k,(x_i,y_i) \in P$； + $(x_1,y_1)=(1,A_1),(x_k,y_k)=(n,A_n)$； + $\forall 1 \le i < k,|x_i-x_{i+1}|+|y_i-y_{i+1}|\le 1$。 3. 规定一个连通点集 $P$ 是“最小连通点集”，当且仅当对于任意连通点集 $Q$，有 $|P| \le |Q|$。 5. 设所有“最小连通点集”的并集为 $P'$。规定 $F(A)=|P'|$。 小明想要对于这个数列 $A$ 求出 $F(A)$ 的值。这是一个简单的问题。 但是 $A$ 中一些数变成了 $0$。小明需要将变为 $0$ 的数重新改为 $[1,V]$ 中的整数。设有 $k$ 个 $0$，则修改方式共 $V^k$ 种。 求出每种修改方式得到的新数列 $A$ 的 $F(A)$ 之和 $G$。 为了方便，仅需输出 $G \bmod 998244353$ 的值。

第一行，$2$ 个整数 $n,V$。 第二行，$n$ 个整数 $A_1,A_2,\cdots,A_n$。

输出一行 $G \bmod 998244353$ 的值。

#### 样例解释： $A$ 可能为 $\{2,1,1\}$ 也可能是 $\{2,2,1\}$。 $F(\{2,1,1\})=4，F(\{2,2,1\})=5$。故 $G=4+5=9$。 #### 数据范围 对于 $100\%$ 的数据，$1 \le n,V \le 1000$，且 $0 \le a_i \le V$。 ::cute-table{tuack} | 测试点 | $n \le$ | $V \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1$ | $1$ | $1000$ | $a_i \ne 0$ | | $2 \sim 3$ | $1000$ | ^ | ^ | | $4$ | $7$ | $8$ | | | $5 \sim 8$ | $50$ | $1000$ | ^ | | $9 \sim 10$ | $1000$ | $50$ | ^ | | $11 \sim 20$ | $1000$ | $1000$ | ^ | | Extra（见 [SCG3](https://scg3.piaoztsdy.cn/p/239)） | $1000$ | $10^9$ | ^ |