AT_nomura2020_d.Urban Planning

有 $N$ 个编号为 $1, 2, \cdots, N$ 的城镇。

现在计划修建若干条双向道路，每条道路连接两个不同的城镇。目前，城镇之间还没有任何道路。

在这个计划中，每个城镇都要求选择另一个城镇，并且希望能够通过一条或多条道路到达所选的城镇。

$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$ 取模后输出。

输入通过标准输入给出，格式如下：

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

对于每一种要求方式，求出满足所有城镇要求所需修建道路数的最小值，将这些最小值的总和对 $10^9+7$ 取模后输出。

限制条件

• $2 \leq N \leq 5000$
• $P_i = -1$ 或 $1 \leq P_i \leq N$
• $P_i \neq i$
• 所有输入均为整数

样例解释 1

存在如下 $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

有时一开始所有要求就已经确定，只存在 $1$ 种方式。

由 ChatGPT 4.1 翻译