题目背景

译自 COCI 2023/2024 Contest #3 T5「Slučajna Cesta」

题目描述

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)$，表示第 $i+1$ 个公园和第 $p_i$ 个公园之间有一条道路。

第三行 $n$ 个整数 $v_i\ (0\le v_i\le 10^6)$，表示第 $i$ 个公园的美丽值。

输出格式

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

2
1
2 1

500000006
2

3
1 1
8 8 8

14
14
14

11
1 1 1 2 3 4 1 2 6 2
1 1000 5 3 18 200 8 9 0 2 2

968750272
610352580
450521029
536458466
199219275
662760680
190972315
90277951
824219264
941840425
532552597

提示

样例解释 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 从第一个公园出发，他会随机选择走哪条路。

子任务