有 $$$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= 0 \pmod{10^9+7}$$$。返回 $$$P \cdot Q^{-1}$$$ 模 $$$10^9+7$$$ 的值。
输入
第一行包含一个整数 $$$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 \not= -1$$$ 则保证 $$$a_{a_i} =-1$$$ (也就是说,所有正在跟踪的初创公司都处于活动状态)。
输出
打印一个整数,即进程以一次活动启动结束所需的预期天数,以 $$$10^9+7$$$ 为模。
示例
输入 #1
3 -1 -1 -1
输出 #1
3
输入 #2
2 2 -1
输出 #2
0
输入 #3
40 3 3 -1 -1 4 4 -1 -1 -1 -1 -1 10 10 10 10 10 10 4 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 3 3 3 3 3 3 3
输出 #3
755808950
注意
在第一个样本中,有 3 个活跃的初创公司,标记为 $$$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$$$。
对于第二个示例,只有一个活动启动,因此我们需要零日。
对于最后一个示例,请记住将答案对 $$$10^9+7$$$ 取模。