分数: 600 点
问题陈述
给你一个整数 N。 整数序列 x=(x_1,x_2,\cdots,x_N) 长度 N 被称为 好 序列当且仅当满足以下条件时:
- 每个元素 x 是介于 1 和 N,包括在内。
- 对于每个整数 i (1 \leq i \leq N), 中没有位置 出现 x 其中 i 出现 i+1 或连续多次。
给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N。 的每个元素 A is -1 或之间的整数 1 和 N。 求模数 998244353,可以通过替换每个来获得好的序列 -1 in A 之间的整数 1 和 N.
约束
- 1 \leq N \leq 5000
- A_i=-1 or 1 \leq A_i \leq N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
2 -1 -1
示例输出 1
3
您可以通过替换每个序列来获得四个序列 -1 之间的整数 1 和 2.
A=(1,1) 不是一个好的序列,因为 1 连续出现两次。
其他序列 A=(1,2),(2,1),(2,2) 都很好。
因此,答案是 3.
示例输入 2
3 2 -1 2
示例输出 2
2
示例输入 3
4 -1 1 1 -1
示例输出 3
0
示例输入 4
20 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1
示例输出 4
128282166