题目描述

给定一个整数 $N$。当且仅当长度为 $N$ 的整数序列 $x=(x_1,x_2,\cdots,x_N)$ 满足以下条件时，称其为好数列。

• $x$ 的每个元素都是 $1$ 到 $N$ 之间的整数。
• 对于每个整数 $i$（$1\leq i\leq N$），在 $x$ 中不存在 $i$ 连续出现 $i+1$ 次或更多次的位置。

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。$A$ 的每个元素要么是 $-1$，要么是 $1$ 到 $N$ 之间的整数。请计算将每个 $-1$ 替换为 $1$ 到 $N$ 之间的整数后，可以得到多少个好数列，并对 $998244353$ 取模。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出答案。

样例 1

输入

2
-1 -1

输出

3

样例 2

输入

3
2 -1 2

输出

2

样例 3

输入

4
-1 1 1 -1

输出

0

样例 4

输入

20
9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1

输出

128282166

说明/提示

限制条件

• $1\leq N\leq 5000$
• $A_i=-1$ 或 $1\leq A_i\leq N$
• 输入的所有值均为整数。

样例解释 1

将每个 $-1$ 替换为 $1$ 或 $2$ 后，共有 $4$ 种数列。对于 $A=(1,1)$，$1$ 连续出现了 $2$ 次，因此不是好数列。对于 $A=(1,2),(2,1),(2,2)$，它们都是好数列。因此答案是 $3$。

由 ChatGPT 4.1 翻译