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 $ C = \{1, \dots, n\} \setminus A $ be the set of acquired startups.
For each $ i \in C $, let $ f(i) \in A $ denote the active startup that $ i $ follows.
Define the **structure** as a directed forest: each $ a \in A $ is a root, and each acquired startup $ i \in C $ is a child of $ f(i) $.
Let $ s_a = |\{ i \in C \mid f(i) = a \}| $ be the number of direct acquired startups under active startup $ a \in A $.
Let $ k = |A| $ be the number of active startups initially.
**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. The graph defined by $ f $ is a forest of $ k $ rooted trees, each root in $ A $.
**Process**
Each day:
- Choose **uniformly at random** a pair of distinct active startups $ (u, v) \in A \times A $, $ u \ne v $.
- $ u $ acquires $ v $:
- $ v $ becomes acquired, and now follows $ u $.
- All startups previously following $ v $ now follow $ u $.
- $ v $ is removed from $ A $, added to $ C $.
- $ u $'s direct acquired count increases by $ s_v + 1 $.
- Repeat until $ |A| = 1 $.
**Objective**
Compute the **expected number of days** until $ |A| = 1 $, starting from $ k = |A| $ active startups with given tree structures.
Let $ E(k; s_1, s_2, \dots, s_k) $ denote the expected number of days given $ k $ active startups with direct acquired counts $ s_1, \dots, s_k $.
The process depends **only** on $ k $, not on the internal structure of the trees, because when an active startup is acquired, all its descendants are transferred to the acquirer — so only the number of active startups matters for transition probabilities.
Thus, define $ E(k) $ as the expected number of days to reduce from $ k $ active startups to 1, regardless of tree sizes.
**Transition**
At state $ k \ge 2 $:
- Number of ordered pairs $ (u,v) $ with $ u \ne v $: $ k(k-1) $
- Each such pair is chosen uniformly.
- After $ u $ acquires $ v $, the number of active startups becomes $ k - 1 $.
So:
$$
E(k) = 1 + \frac{1}{k(k-1)} \sum_{u \ne v} E(k-1) = 1 + E(k-1)
$$
Thus:
$$
E(k) = E(k-1) + 1
$$
With base case:
$$
E(1) = 0
$$
Therefore:
$$
E(k) = k - 1
$$
But wait — this assumes that **every transition reduces $ k $ by 1**, which is true, and **all transitions are equally likely**, which is also true.
Hence, regardless of the initial tree structure, the expected number of days is simply $ k - 1 $, where $ k = |A| $.
**Final Answer**
Let $ k = |\{ i \mid a_i = -1 \}| $.
Then the expected number of days is $ k - 1 $.
Return $ (k - 1) \mod (10^9 + 7) $.
**Output**
$$
(k - 1) \mod (10^9 + 7)
$$