[ARC140D] One to One

你有一个长度为 $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$ 取模的结果。

[problemUrl]: https://atcoder.jp/contests/arc140/tasks/arc140_d 全ての要素が $ 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 $

答えを出力せよ。

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 $ です。