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$:
<center>Active startups are shown in red.
</center>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:
<center></center>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:
<center></center>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$.
## Input
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).
## Output
Print a single integer, the expected number of days needed for the process to end with exactly one active startup, modulo $10^9+7$.
[samples]
## Note
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$.
有 $n$ 家初创公司。初创公司可以是 _活跃的_ 或 _被收购的_。如果一家初创公司是 _被收购的_，则意味着它恰好有一家 _活跃的_ 初创公司是它所跟随的。一家活跃的初创公司可以有任意多家被收购的初创公司跟随它。活跃的初创公司不能跟随任何其他公司。
以下步骤会持续进行，直到恰好剩下一活跃的初创公司。以下一系列步骤恰好耗时 1 天。
例如，可能发生以下情形：假设 $A$、$B$ 是活跃的初创公司，$C$、$D$、$E$ 是跟随 $A$ 的被收购公司，$F$、$G$ 是跟随 $B$ 的被收购公司：
#cf_span(class=[tex-font-size-small], body=[Active startups are shown in red.])
如果 $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}$ 对 $10^9 + 7$ 取模的值。
第一行包含一个整数 $n$（$2 \leq n \leq 500$），表示初创公司的数量。
下一行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, 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$（即所有被跟随的公司都是活跃的）。
输出一个整数，表示该过程结束时恰好剩下一活跃初创公司所需的期望天数，对 $10^9 + 7$ 取模。
在第一个样例中，有三家公司 $1$、$2$ 和 $3$ 是活跃的，没有被收购的公司。以下是其中一个可能的场景：
此时，只剩下一活跃的初创公司，该序列共耗时 $4$ 天。可以证明期望天数为 $3$。
对于第二个样例，只有一家活跃公司，因此需要 $0$ 天。
对于最后一个样例，请记得对答案取模 $10^9 + 7$。
## Input
第一行包含一个整数 $n$（$2 \leq n \leq 500$），表示初创公司的数量。下一行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, 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$（即所有被跟随的公司都是活跃的）。
## Output
输出一个整数，表示该过程结束时恰好剩下一活跃初创公司所需的期望天数，对 $10^9 + 7$ 取模。
[samples]
## Note
在第一个样例中，有三家公司 $1$、$2$ 和 $3$ 是活跃的，没有被收购的公司。以下是其中一个可能的场景：
初创公司 $1$ 收购了初创公司 $2$（该状态可用数组 $[-1, 1, -1]$ 表示）
初创公司 $3$ 收购了初创公司 $1$（该状态可用数组 $[3, -1, -1]$ 表示）
初创公司 $2$ 收购了初创公司 $3$（该状态可用数组 $[-1, -1, 2]$ 表示）
初创公司 $2$ 收购了初创公司 $1$（该状态可用数组 $[2, -1, 2]$ 表示）
此时，只剩下一活跃的初创公司，该序列共耗时 $4$ 天。可以证明期望天数为 $3$。
对于第二个样例，只有一家活跃公司，因此需要 $0$ 天。
对于最后一个样例，请记得对答案取模 $10^9 + 7$。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of startups.
Let $ A \subseteq \{1, 2, \dots, n\} $ be the set of active startups:
$$ A = \{ i \in \{1, \dots, n\} \mid a_i = -1 \} $$
Let $ f: \{1, \dots, n\} \setminus A \to A $ be the function mapping each acquired startup to its active follower:
$$ f(i) = a_i \quad \text{for } a_i \ne -1 $$
Let $ C: A \to \mathbb{Z}_{\ge 0} $ be the count function for acquired startups under each active startup:
$$ C(j) = |\{ i \in \{1, \dots, n\} \setminus A \mid f(i) = j \}| $$
**Constraints**
1. $ 2 \le n \le 500 $
2. For all $ i \in \{1, \dots, n\} $:
- $ a_i = -1 $ or $ 1 \le a_i \le n $
- If $ a_i \ne -1 $, then $ a_{a_i} = -1 $ (i.e., every follower is active)
3. $ |A| \ge 1 $
**Objective**
Let $ k = |A| $ be the initial number of active startups.
The process proceeds in days: each day, two distinct active startups $ u, v \in A $ are chosen uniformly at random, and $ u $ acquires $ v $ (i.e., $ v $ becomes acquired under $ u $, and all startups previously acquired by $ v $ become acquired under $ u $).
After this operation:
- $ v $ is removed from $ A $,
- $ u $ gains $ C(v) + 1 $ new acquired startups (including $ v $ itself),
- $ C(u) \leftarrow C(u) + C(v) + 1 $,
- $ C(v) \leftarrow 0 $,
The process ends when $ |A| = 1 $.
Let $ \mathbb{E}[k] $ denote the expected number of days to reduce $ k $ active startups to 1.
We are to compute $ \mathbb{E}[k] \mod (10^9 + 7) $, expressed as $ P \cdot Q^{-1} \mod (10^9 + 7) $, where $ \mathbb{E}[k] = \frac{P}{Q} $ in lowest terms.
**Recurrence**
Define $ E(k) $ as the expected number of days to reduce $ k $ active startups to 1.
Then:
$$ E(1) = 0 $$
$$ E(k) = 1 + \frac{2}{k(k-1)} \sum_{1 \le i < j \le k} E(k - 1) \quad \text{for } k \ge 2 $$
But since every pair of active startups leads to the same state (reduction of count by 1), and there are $ \binom{k}{2} $ pairs, we have:
$$ E(k) = 1 + E(k - 1) \quad \text{for } k \ge 2 $$
Thus:
$$ E(k) = k - 1 $$
Therefore, the expected number of days is $ |A| - 1 $.
**Final Output**
Let $ k = |A| $. Output $ (k - 1) \mod (10^9 + 7) $.
**Note**: The structure of acquired startups (i.e., $ C(j) $) does not affect the expected number of days, as the process depends only on the number of active startups, not their subtree sizes. The transition probability depends only on the count of active startups, and each merge reduces the count by exactly 1, uniformly at random.
Thus:
$$ \boxed{E = |A| - 1} $$