CF1025G.Company Acquisitions

There are $n$ startups. Startups can be active or acquired. If a startup is acquired, then that means it has exactly one active startup that it is following. An active startup can have arbitrarily many acquired startups that are following it. An active startup cannot follow any other startup.

The following steps happen until there is exactly one active startup. The following sequence of steps takes exactly 1 day.

1. Two distinct active startups $A$, $B$, are chosen uniformly at random.
2. A fair coin is flipped, and with equal probability, $A$ acquires $B$ or $B$ acquires $A$ (i.e. if $A$ acquires $B$, then that means $B$'s state changes from active to acquired, and its starts following $A$).
3. When a startup changes from active to acquired, all of its previously acquired startups become active.

For example, the following scenario can happen: Let's say $A$, $B$ are active startups. $C$, $D$, $E$ are acquired startups under $A$, and $F$, $G$ are acquired startups under $B$:

Active startups are shown in red.

If $A$ acquires $B$, then the state will be $A$, $F$, $G$ are active startups. $C$, $D$, $E$, $B$ are acquired startups under $A$. $F$ and $G$ have no acquired startups:

If instead, $B$ acquires $A$, then the state will be $B$, $C$, $D$, $E$ are active startups. $F$, $G$, $A$ are acquired startups under $B$. $C$, $D$, $E$ have no acquired startups:

You are given the initial state of the startups. For each startup, you are told if it is either acquired or active. If it is acquired, you are also given the index of the active startup that it is following.

You're now wondering, what is the expected number of days needed for this process to finish with exactly one active startup at the end.

It can be shown the expected number of days can be written as a rational number $P/Q$, where $P$ and $Q$ are co-prime integers, and $Q \not= 0 \pmod{10^9+7}$. Return the value of $P \cdot Q^{-1}$ modulo $10^9+7$.

共有 $n$ 家初创公司。每家初创公司处于“活跃”或“被收购”状态。若一家初创公司被收购，则它恰好正在追随一家活跃的初创公司。一家活跃的初创公司可以被任意数量的被收购初创公司所追随。而一家活跃的初创公司不能追随任何其他初创公司。

以下步骤将不断重复，直至仅剩一家活跃的初创公司为止。该步骤序列恰好耗时 1 天：

1. 随机、均匀地选择两家不同的活跃初创公司 $A$ 和 $B$；
2. 抛一枚公平硬币：以相等的概率，要么 $A$ 收购 $B$，要么 $B$ 收购 $A$（例如，若 $A$ 收购 $B$，则 $B$ 的状态由“活跃”变为“被收购”，并开始追随 $A$）；
3. 当一家初创公司由“活跃”变为“被收购”时，其原先所有被收购的下属初创公司均变为“活跃”。

例如，如下情形可能发生：设 $A$、$B$ 为活跃初创公司；$C$、$D$、$E$ 是追随 $A$ 的被收购初创公司；$F$、$G$ 是追随 $B$ 的被收购初创公司：

图中活跃初创公司以红色显示。

若 $A$ 收购 $B$，则新状态为：$A$、$F$、$G$ 为活跃初创公司；$C$、$D$、$E$、$B$ 均为追随 $A$ 的被收购初创公司；$F$ 和 $G$ 没有下属被收购初创公司：

反之，若 $B$ 收购 $A$，则新状态为：$B$、$C$、$D$、$E$ 为活跃初创公司；$F$、$G$、$A$ 为追随 $B$ 的被收购初创公司；$C$、$D$、$E$ 没有下属被收购初创公司：

你已知所有初创公司的初始状态：对每家公司，你被告知其是“被收购”还是“活跃”；若为“被收购”，你还被告知它所追随的活跃初创公司的编号。

你现在想知道：该过程结束（即最终仅剩一家活跃初创公司）所需的期望天数是多少？

可以证明，该期望天数可表示为一个既约有理数 $P/Q$，其中 $P$ 与 $Q$ 互质，且 $Q \not\equiv 0 \pmod{10^9+7}$。请返回 $P \cdot Q^{-1} \bmod (10^9+7)$ 的值。

The first line contains a single integer $n$ ($2 \leq n \leq 500$), the number of startups.

The next line will contain $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($a_i = -1$ or $1 \leq a_i \leq n$). If $a_i = -1$, then that means startup $i$ is active. Otherwise, if $1 \leq a_i \leq n$, then startup $i$ is acquired, and it is currently following startup $a_i$. It is guaranteed if $a_i \not= -1$, then $a_{a_i} =-1$ (that is, all startups that are being followed are active).

第一行包含一个整数 $n$（$2 \leq n \leq 500$），表示初创公司的数量。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（每个 $a_i$ 要么为 $-1$，要么满足 $1 \leq a_i \leq n$）。若 $a_i = -1$，则表示第 $i$ 家初创公司处于活跃状态；否则，若 $1 \leq a_i \leq n$，则表示第 $i$ 家初创公司已被收购，且当前正追随第 $a_i$ 家初创公司。题目保证：若 $a_i \neq -1$，则必有 $a_{a_i} = -1$（即所有被追随的初创公司均为活跃状态）。

Print a single integer, the expected number of days needed for the process to end with exactly one active startup, modulo $10^9+7$.

输出一个整数，表示该过程最终恰好剩下一个活跃创业公司所需的期望天数，对 $10^9+7$ 取模。

In the first sample, there are three active startups labeled $1$, $2$ and $3$, and zero acquired startups. Here's an example of how one scenario can happen

1. Startup $1$ acquires startup $2$ (This state can be represented by the array $[-1, 1, -1]$)
2. Startup $3$ acquires startup $1$ (This state can be represented by the array $[3, -1, -1]$)
3. Startup $2$ acquires startup $3$ (This state can be represented by the array $[-1, -1, 2]$).
4. Startup $2$ acquires startup $1$ (This state can be represented by the array $[2, -1, 2]$).

At this point, there is only one active startup, and this sequence of steps took $4$ days. It can be shown the expected number of days is $3$.

For the second sample, there is only one active startup, so we need zero days.

For the last sample, remember to take the answer modulo $10^9+7$.

在第一个样例中，有三个活跃的初创公司，编号为 $1$、$2$ 和 $3$，且没有被收购的初创公司。以下是一个可能的发生过程示例：

1. 初创公司 $1$ 收购初创公司 $2$（该状态可用数组 $[-1, 1, -1]$ 表示）；
2. 初创公司 $3$ 收购初创公司 $1$（该状态可用数组 $[3, -1, -1]$ 表示）；
3. 初创公司 $2$ 收购初创公司 $3$（该状态可用数组 $[-1, -1, 2]$ 表示）；
4. 初创公司 $2$ 收购初创公司 $1$（该状态可用数组 $[2, -1, 2]$ 表示）。

此时仅剩一家活跃的初创公司，该过程共耗时 $4$ 天。可以证明，所需天数的期望值为 $3$。

在第二个样例中，仅有一家活跃的初创公司，因此需要 $0$ 天。

在最后一个样例中，请记得将答案对 $10^9+7$ 取模。