题目描述

全ての要素が $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$ で割ったあまりを求めてください。

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

你有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，其中每个元素都是 $[1,n]$ 中的整数。

初始时有编号为 $1 \sim n$ 的 $n$ 个节点，对于每个 $1\leq i \leq n$，从 $i$ 向 $a_i$ 连一条无向边。$a_i=-1$ 表示 $a_i$ 还没有确定。你需要对所有可能的 $a$ 序列求出图中连通块数量的和对 $998244353$ 取模的结果。

3
-1 1 3

5

1
1

1

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

433760

提示

制約

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

Sample Explanation 1

$X$ として条件を満たすものは以下の $3$ 通りがあります。 - $X=(1,1,3)$ の時、問題の答えは $2$ です。 - $X=(2,1,3)$ の時、問題の答えは $2$ です。 - $X=(3,1,3)$ の時、問題の答えは $1$ です。 よって答えは $2+2+1=5$ です。