连通块数之和

时间限制：2s
空间限制：1024MB

题目描述

对一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$，定义 $f(A)$ 如下：先建立一个有 $N$ 个顶点且没有边的无向图，顶点编号为 $1$ 到 $N$；对所有满足 $1\le i<j\le N$ 的整数对 $(i,j)$，若 $A_i\le A_j$，就在顶点 $i$ 与顶点 $j$ 之间连边。令最终图中的连通块数为 $f(A)$。

给定长度为 $N$ 的序列 $B=(B_1,B_2,\ldots,B_N)$，其中每个元素为 $-1$ 或 $1$ 到 $M$ 之间的整数。将所有 $-1$ 分别替换为 $1$ 到 $M$ 之间的整数，得到序列 $B'$。若 $B$ 中有 $q$ 个 $-1$，则一共有 $M^q$ 种可能的 $B'$。

求所有可能的 $B'$ 的 $f(B')$ 之和，对 $998244353$ 取模。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数 $B_1,B_2,\ldots,B_N$。

输出格式

输出答案对 $998244353$ 取模的结果。

样例输入 1

3 3
2 -1 1

样例输出 1

6

样例输入 2

10 8
-1 7 -1 -1 -1 2 -1 1 -1 2

样例输出 2

329785

样例输入 3

11 12
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

样例输出 3

529513150

数据范围

• $2\le N\le2000$；
• $1\le M\le2000$；
• $B_i=-1$ 或 $1\le B_i\le M$。