Rắn độc

Time limit: 3.0s , Memory limit: 512M , Points: 100 (partial)

Thành phố có tổng cộng $n$ ~n~ địa điểm được đánh số từ $1$ ~1~ đến $n$ ~n~ và $n-1$ ~n-1~ con đường nối hai chiều sao cho xuất phát từ một địa điểm bất kỳ có thể đến được mọi đại điểm khác. Mỗi địa điểm có một độ thân thiện $v_i$ ~v_i~.

Việc di chuyển trong thành phố giữa các địa điểm như sau: Khi đứng tại một địa điểm, chọn ngẫu nhiên một trong các địa điểm tiếp theo có đường nối với địa điểm hiện tại với xác suất như nhau, sau đó đi đến địa điểm được chọn. Độ thân thiện của việc di chuyển là tổng độ thân thiện của các địa điểm đã đi qua.

Trên mỗi đường đi nối giữa hai địa điểm xuất hiện một con rắn độc mang một trong hai màu xanh hoặc đỏ với xác suất như nhau. Rắn xanh sẽ cắn người di chuyển từ địa điểm có số thứ tự thấp hơn đến địa điểm có số thứ tự cao hơn trên đường nối đó, ngược lại rắn đỏ sẽ cắn người di chuyển từ địa điểm có số thứ tự cao hơn đến địa điểm có số thứ tự thấp hơn. Vì vậy trong quá trình di chuyển, nếu đang đứng ở một địa điểm, phải chọn ngẫu nhiên một trong các địa điểm tiếp theo có đường nối với địa điểm hiện tại sao cho không bị rắn cắn (các địa điểm tiếp theo thỏa mãn có xác suất được chọn như nhau).

Nhiệm vụ của bạn hãy trả lời câu hỏi "Nếu quá trình di chuyển xuất phát tại địa điểm $i$ ~i~ $(1 \le i \le n)$ ~(1 \le i \le n)~ thì giá trị kỳ vọng của độ thân thiện của việc di chuyển là bao nhiêu?"

Input

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(2 \le n \le 10^6)$ ~(2 \le n \le 10^6)~.
Dòng thứ hai chứa $n-1$ ~n-1~ số nguyên $p_i$ ~p_i~ $(1 \le i < n; \; 1 \le p_i < i)$ ~(1 \le i < n; \; 1 \le p_i < i)~ là số thứ tự của địa điểm có đường nối với địa điểm $i + 1$ ~i + 1~.
Dòng cuối cùng chứa $n$ ~n~ số nguyên $v_i$ ~v_i~ $(0 \le v_i \le 10^6)$ ~(0 \le v_i \le 10^6)~.

Output

In ra trên $n$ ~n~ dòng, dòng thứ $i$ ~i~ chứa số nguyên là giá trị kỳ vọng của độ thân thiện của việc di chuyển nếu xuất phát từ đỉnh $i$ ~i~. Dễ dàng nhận thấy rằng kết quả có dạng $\frac{a}{b}$ ~\frac{a}{b}~, vì vậy cần chia lấy dư kết quả cho $10^9 + 7$ ~10^9 + 7~.

Samples

Sample Input 1

2
1
2 1

Sample Output 1

500000006
2

Sample Input 2

3
1 1
8 8 8

Sample Output 2

14
14
14

Sample Input 3

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

Sample Output 3

Scoring

Subtask $1$ ~1~ với $10\%$ ~10\%~ số điểm: $n \le 10$ ~n \le 10~
Subtask $2$ ~2~ với $20\%$ ~20\%~ số điểm: $n \le 1000$ ~n \le 1000~
Subtask $3$ ~3~ với $30\%$ ~30\%~ số điểm: Trong các giá trị $p_i$ ~p_i~ không có giá trị nào xuất hiện quá hai lần
Subtask $4$ ~4~ với $40\%$ ~40\%~ số điểm: Không có ràng buộc gì thêm

Clarification

Ở ví dụ đầu tiên, giá trị kỳ vọng của độ thân thiện nếu xuất phát từ địa điểm $1$ ~1~ là $\frac{5}{2}$ ~\frac{5}{2}~ và xuất phát từ địa điểm $2$ ~2~ là $2$ ~2~.
Ở ví dụ thứ hai, xác suất để cả hai con rắn ở hai đường nối đều màu đỏ là $\frac{1}{4}$ ~\frac{1}{4}~ và trong trường hợp này, nếu xuất phát từ địa điểm $1$ ~1~ đều có thể đi đến địa điểm $2$ ~2~ hoặc địa điểm $3$ ~3~ mà không bị rắn cắn.