[ARC169C] Not So Consecutive

给一个长度为 $n$ 的序列 $A$，其中一些位置为 $-1$，其余位置的值域均在 $[1,n]$ 之间。 你要给所有 $-1$ 的位置填一个 $[1,n]$ 之间的整数，要求满足： - 对于任意 $[1,n]$ 之间的整数 $i$，不能在 $A$ 中**连续**出现超过 $i$ 次。 求方案数，答案对 $998244353$ 取模。$n\le 5000$。 Translated by Aigony.

[problemUrl]: https://atcoder.jp/contests/arc169/tasks/arc169_c 整数 $ N $ が与えられます． 長さ $ N $ の整数列 $ x=(x_1,x_2,\cdots,x_N) $ は，以下の条件を満たすとき（そしてそのときのみ）**よい**数列と呼ばれます． - $ x $ の各要素は $ 1 $ 以上 $ N $ 以下の整数である． - 各整数 $ i $ ($ 1\ \leq\ i\ \leq\ N $) に対し，$ i $ が $ i+1 $ 個以上連続して並ぶような場所が $ x $ 内に存在しない． 長さ $ N $ の整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます． $ A $ の各要素は $ 1 $ 以上 $ N $ 以下の整数もしくは $ -1 $ です． それぞれの $ -1 $ を $ 1 $ 以上 $ N $ 以下の整数に置き換えることで得られるよい数列の個数を $ 998244353 $ で割ったあまりを求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ．

2
-1 -1

3

3
2 -1 2

2

4
-1 1 1 -1

0

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 $ - 入力される値はすべて整数． ### Sample Explanation 1 それぞれの $ -1 $ を $ 1 $ 以上 $ 2 $ 以下の整数で置き換えて得られる数列は $ 4 $ 通りあります． ここで $ A=(1,1) $ について考えると，$ 1 $ が $ 2 $ 個連続してしまうためよい数列ではありません． それ以外の $ A=(1,2),(2,1),(2,2) $ について考えると，これらはすべてよい数列です． よって答えは $ 3 $ です．