配点 : $700$ 点

問題文

$1, 2, \cdots, N$ の番号がついた $N$ 個の町があります。

現在、$2$ つの相異なる町を双方向に結ぶ道をいくつか作ることが計画されています。現時点では、町を結ぶ道はありません。

この計画において、各町は他の町を $1$ つ選んで、道を $1$ 本以上使ってその町に移動できるように要請します。

$N$ 個の町の要請は配列 $P_1, P_2, \cdots, P_N$ で表され、町 $i$ の要請は、$P_i = -1$ のときまだ決定されていないこと、$1 \leq P_i \leq N$ であるとき町 $P_i$ を選んだことを表します。

$P_i = -1$ である町の個数を $K$ 個としたとき、全体では $(N-1)^K$ 通りの要請方法が考えられます。それぞれの要請方法について、すべての町の要請を満たすために作る必要がある道の本数の最小値を求め、その総和を $10^9+7$ で割った余りを出力してください。

制約

• $2 \leq N \leq 5000$
• $P_i = -1$ または $1 \leq P_i \leq N$
• $P_i \neq i$
• 入力は全て整数である

入力

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

$N$

$P_1$ $P_2$ $\cdots$ $P_N$

出力

それぞれの要請方法について、すべての町の要請を満たすために作る必要がある道の本数の最小値を求め、その総和を $10^9+7$ で割った余りを出力せよ。

4
2 1 -1 3

8

要請方法としては次の $3$ 通りがあります。

• $P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3$ とする。このとき、例えば道 $(1,2),(1,3),(3,4)$ の $3$ つを作ることですべての町の要請を満たすことができ、これが最小です。
• $P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3$ とする。このとき、例えば道 $(1,2),(1,3),(3,4)$ の $3$ つを作ることですべての町の要請を満たすことができ、これが最小です。
• $P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3$ とする。このとき、例えば道 $(1,2),(3,4)$ の $2$ つを作ることですべての町の要請を満たすことができ、これが最小です。

必ずしも町 $i$ と町 $P_i$ が直接繋がっている必要がないことに注意してください。

よって、総和は $8$ です。

2
2 1

1

初めから要請が $1$ 通りに決まっている場合もあります。

10
2 6 9 -1 6 9 -1 -1 -1 -1

527841