配点 : $700$ 点

問題文

全ての要素が $1$ 以上 $N$ 以下である長さ $N$ の整数列 $X=(X_1,X_2,\dots,X_N)$ に対して次の問題を考え、その答えを $f(X)$ とします。

$$N$$$$G$$$$G$$$$G$$$$N$$$$i$$$$i$$$$X_i$$$$G$$長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。各 $A_i$ は $1$ 以上 $N$ 以下の整数あるいは $-1$ です。 $$

全ての要素が $1$ 以上 $N$ 以下である長さ $N$ の整数列 $X=(X_1,X_2,\dots,X_N)$ であって、$A_i \neq -1 \Rightarrow A_i = X_i$ を満たすものを考えます。そのような全ての $X$ に対する $f(X)$ の総和を $998244353$ で割ったあまりを求めてください。

制約

• $1 \le N \le 2000$
• $A_i$ は $1$ 以上 $N$ 以下あるいは $-1$ である。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力せよ。

3
-1 1 3

5

$X$ として条件を満たすものは以下の $3$ 通りがあります。

• $X=(1,1,3)$ の時、問題の答えは $2$ です。
• $X=(2,1,3)$ の時、問題の答えは $2$ です。
• $X=(3,1,3)$ の時、問題の答えは $1$ です。

よって答えは $2+2+1=5$ です。

1
1

1

8
-1 3 -1 -1 8 -1 -1 -1

433760