問題文

パ研君は、次の問題を解いています。

N 頂点の木が与えられる。頂点には 1, 2, \ldots, N の番号が付けられている。

各頂点について、その頂点から最も離れた頂点を一つ求めよ。複数ある場合はどれを求めてもいい。

パ研君はこの問題を解き、 1 \leq i \leq N について頂点 i から最も離れた頂点のうち一つが頂点 A_i であると分かりました。

しかしなんという事でしょう、せっかく問題を解けたのに、元の木や A の一部の値が分からなくなってしまいました。あなたはパ研君のために、数列 A を復元してあげたいと考えました。

今あなたには長さ N の数列 B が与えられます。この数列は残っている A の情報を表しています。このとき、次の全ての条件を満たす長さ N の数列 A を考えます。

• B_i \neq -1 ならば A_i = B_i である
• ある木が存在し、 1 \leq i \leq N について、頂点 i から最も離れた頂点の一つが頂点 A_i である

このような条件を満たす A がいくつあるか、パ研君に教えてあげてください。ただし、パ研君が問題を解き間違えていた可能性があるため、条件を満たす A が存在しない場合もあります。

なお、答えは大きくなる場合があるので、代わりに答えを 998244353 で割ったあまりを求めて下さい。

制約

• 入力は全て整数
• 1 \leq N \leq 2 \times 10^5
• 1 \leq B_i \leq N または B_i = -1 (1 \leq i \leq N)

小課題

1. (100 点) B_i \neq -1 (1 \leq i \leq N)
2. (100 点) 1 \leq N \leq 20
3. (100 点) 1 \leq N \leq 2000
4. (300 点) 追加の制約はない

入力例 1

3
2 -1 -1

出力例 1

3

A=(2, 1, 1), (2, 1, 2), (2, 3, 2) の 3 通りが考えられます。

この入出力例は小課題 2, 3, 4 の制約を満たします。

入力例 2

8
-1 8 7 5 -1 1 2 3

出力例 2

47

この入力例は小課題 2, 3, 4 の制約を満たします。

入力例 3

4
1 2 3 4

出力例 3

0

どうやらパ研君は問題を解き間違えていたようですが、この入力例は全ての小課題の制約を満たします。