不那么连续

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

题目描述

给定整数 $N$。一个长度为 $N$ 的整数序列 $x=(x_1,x_2,\ldots,x_N)$ 称为好序列，当且仅当它满足以下条件：每个元素都是 $1$ 到 $N$ 之间的整数；对于每个整数 $i$，序列中不存在连续 $i+1$ 个或更多元素都等于 $i$ 的位置。

现在给定长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$，其中每个元素是 $-1$ 或 $1$ 到 $N$ 之间的整数。把每个 $-1$ 替换为 $1$ 到 $N$ 之间的任意整数，求能得到多少个好序列。答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出满足条件的替换方案数对 $998244353$ 取模后的结果。

样例输入 1

2
-1 -1

样例输出 1

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

数据范围

对于所有数据，$1\le N\le5000$，且 $A_i=-1$ 或 $1\le A_i\le N$。