分数: 600 点
问题陈述
对于序列 A = (A_1, \ldots, A_N) 长度 N,定义 f(A) 如下。
- 准备一个图表 N 顶点标记 1 to N 和零边缘。对于每个整数对 (i, j) 满意 1 \leq i < j \leq N,如果 A_i \leq A_j,绘制连接顶点的双向边 i 和 j。定义 f(A) 作为结果图中连接分量的数量。
给你一个序列 B = (B_1, \ldots, B_N) 长度 N。的每个元素 B is -1 或之间的整数 1 和 M,包括在内。
通过替换每次出现的 -1 in B 之间的整数 1 和 M,可以获得 M^q 序列 B',其中 q 是数量 -1 in B.
求总和,模 998244353,属于 f(B') 总体而言 B'.
约束
- 所有输入数字均为整数。
- 2 \leq N \leq 2000
- 1 \leq M \leq 2000
- 每个 B_i is -1 或之间的整数 1 和 M,包括在内。
输入
输入由标准输入按以下格式给出:
N M B_1 \ldots B_N
输出
打印答案。
示例输入 1
3 3 2 -1 1
示例输出 1
6
存在三种可能的序列 B': (2,1,1), (2,2,1),和 (2,3,1).
当 B' = (2,1,1),仅在顶点之间绘制边 2 和 3,因此连接组件的数量为 2。因此, f(B') = 2.
同样, f(B') = 2 为 B' = (2,2,1) 和 f(B') = 2 为 B' = (2,3,1),所以答案是 2 + 2 + 2 = 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
记得求模求和 998244353.