分数: 800 点
问题陈述
对于排列 P = (P_1, \ldots, P_N) of (1, \ldots, N),让 P' = (P'_1, \ldots, P'_N) 是执行一次以下操作得到的排列。
- 对于 i = 1, 2, \ldots, N-1 按此顺序,如果 P_i > P_{i+1},交换 P_i 和 P_{i+1}.
给你一个序列 Q = (Q_1, \ldots, Q_N) 长度 N。每个 Q_i is -1 或之间的整数 1 和 N,包括在内。
求模数 998244353,排列 P of (1, \ldots, N) 这样,对于每个 i,如果 Q_i \neq -1 然后 Q_i = P'_i.
约束
- 所有输入数字均为整数。
- 2 \leq N \leq 5000
- 每个 Q_i is -1 或之间的整数 1 和 N.
- 每个 1,2,\ldots,N 最多出现一次 Q.
输入
输入由标准输入按以下格式给出:
N Q_1 \ldots Q_N
输出
打印答案。
示例输入 1
4 -1 -1 2 4
示例输出 1
6
例如, P = (3,1,4,2) 满足条件。这可以通过以下操作行为来确认。
- 对于 i=1,因为 P_1 > P_2,交换 P_1 和 P_2,导致 P = (1,3,4,2).
- 对于 i=2,因为 P_2 < P_3,什么也不做。
- 对于 i=3,因为 P_3 > P_4,交换 P_3 和 P_4,导致 P = (1,3,2,4).
- 因此, 总共使用了 P' = (1,3,2,4),满意 P'_3=2 和 P'_4=4.
有六种排列 P 满足条件:
- (1,3,4,2)
- (1,4,3,2)
- (3,1,4,2)
- (3,4,1,2)
- (4,1,3,2)
- (4,3,1,2)
示例输入 2
6 -1 -1 -1 -1 2 -1
示例输出 2
120
示例输入 3
15 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 7 -1 -1 -1 -1
示例输出 3
237554682
记住求模数 998244353.