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$ 个公园出发的旅程的期望美观度为 $\frac{a}{b}$（$a, b$ 为整数），则在第 $i$ 行输出 $a \cdot b^{-1} \pmod{10^9 + 7}$，其中 $b^{-1}$ 是 $b$ 在模 $10^9 + 7$ 下的乘法逆元。

子任务

如果你的程序在某个测试点上第一行输出正确，但后续行输出错误，则该测试点将获得 50% 的分数。

子任务的得分等于该子任务中某个测试点所获得的最低分数。

样例

输入 1

2
1
2 1

输出 1

500000006
2

说明 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

3
1 1
8 8 8

输出 2

14
14
14

说明 2

两条蛇都是红色的概率为 $\frac{1}{4}$，在这种情况下，如果 Vito 从第一个公园出发，他会随机选择他要走的道路。

输入 3

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

输出 3

968750272
610352580
450521029
536458466
199219275
662760680
190972315
90277951
824219264
941840425
532552597