Contest Duration: - (local time) (120 minutes) Back to Home
D - One to One /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 頂点の無向グラフ G があります。(G は多重辺や自己ループを含むことがあります。) G の辺は N 本あり、そのうち i 番目の辺は頂点 i と頂点 X_i を繋ぐ辺です。G の連結成分の個数を求めてください。

### 制約

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

### 入力

N
A_1 A_2 \dots A_N


### 入力例 1

3
-1 1 3


### 出力例 1

5


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

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

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

### 入力例 2

1
1


### 出力例 2

1


### 入力例 3

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


### 出力例 3

433760


Score : 700 points

### Problem Statement

For an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N (inclusive), consider the question below, and let f(X) be the answer.

There is an undirected graph G with N vertices (and possibly multi-edges and self-loops). G has N edges, the i-th of which connects Vertex i and Vertex X_i. Find the number of connected components in G.

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N, where each A_i is an integer between 1 and N (inclusive) or -1.

Consider an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N such that A_i \neq -1 \Rightarrow A_i = X_i. Find the sum of f(X) over all such X, modulo 998244353.

### Constraints

• 1 \le N \le 2000
• A_i is between 1 and N (inclusive) or -1.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N


### Sample Input 1

3
-1 1 3


### Sample Output 1

5


There are three sequences X satisfying the requirement, as follows.

• X=(1,1,3), for which the answer to the question is 2.
• X=(2,1,3), for which the answer to the question is 2.
• X=(3,1,3), for which the answer to the question is 1.

### Sample Input 2

1
1


### Sample Output 2

1


### Sample Input 3

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


### Sample Output 3

433760