P10227 [COCI 2023/2024 #3] Slučajna Cesta

**译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T5「[Slučajna Cesta](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

Vito 住在一个有 $n$ 个公园的城市，这些公园编号为 $1$ 到 $n$。这些公园被 $n-1$ 条道路相连，满足任意两公园之间都存在一条路径。每个公园均有一个美丽值，第 $i$ 个公园的美丽值为 $v_i$。 昨晚 Vito 决定在城市中走走，在他游览完一个公园后，他会等概率随机选择一条路，并游览这条路通往的公园。但在出发前，他透过摩天大楼的窗户看到，每条路上都有一条蓝蛇或红蛇。蓝蛇会攻击所有从编号较小的公园前往编号较大的公园的人，红蛇会攻击所有从编号较大的公园前往编号较小的公园的人。由于 Vito 不想被蛇攻击，他决定改变计划，在随机选择道路时只考虑不会被蛇攻击的道路。因为他喜欢长距离行走，所以在至少有一条路他可以安全通过之前，他不会停下脚步。 当 Vito 下楼时，他完全忘记了哪条路上有红蛇或蓝蛇，于是他想知道：「如果每条路上有蓝蛇或红蛇的概率相同，那么我从第 $i$ 个公园开始的路线的美感的期望是多少？」 一条路线的美感是在这条路线上经过的公园的美丽值的和。路线美感的期望定义为对于所有可能的路线，路线的美感乘以 Vito 按这条路线走的概率的乘积之和。

第一行一个整数 $n\ (2\le n\le 10^6)$，表示公园数量。 第二行有 $n-1$ 个整数 $p_i\ (1\le p_i

第 $i$ 行输出 Vito 从第 $i$ 个公园开始的路线的美感的期望。如果这个值为 $\frac{a}{b}$（$a,b$ 为整数），则输出 $ab^{-1} \pmod{10^9+7}$，其中 $b^{-1}$ 是 $b$ 在模 $10^9+7$ 意义下的逆元。

### 样例解释 1 从第一个公园开始的路线的美感的期望是 $2.5\pmod{10^9+7}=\frac{5}{2}\pmod{10^9+7}=5\cdot 2^{-1}\pmod{10^9+7}=5\cdot 500000004\pmod{10^9+7}=500000006\pmod{10^9+7}$，从第二个公园开始的路线的美感的期望是 $2$。 ### 样例解释 2 两条蛇都是红蛇的概率是 $\frac{1}{4}$，这种情况下如果 Vito 从第一个公园出发，他会随机选择走哪条路。 ### 子任务 | 子任务编号 | 附加限制 | 分值 | | :--------: | :--------------------------------: | :--: | | $1$ | $n\le 10$ | $9$ | | $2$ | $n\le 1\ 000$ | $27$ | | $3$ | 序列 $p_i$ 中没有值出现超过 $2$ 次 | $27$ | | $4$ | 无附加限制 | $37$ |