Vito sống ở một thành phố có ~n~ công viên được đánh số từ ~1~ đến ~n~. Các công viên được kết nối với ~n − 1~ con đường sao cho có một đường đi giữa hai cặp công viên bất kỳ. Mỗi công viên đều có một giá trị vẻ đẹp nào đó, giá trị vẻ đẹp của công viên thứ ~i~ là ~v_i~.

Đêm qua Vito quyết định đi lang thang quanh thành phố theo cách mà sau khi ghé thăm một công viên, anh ấy chọn một con đường ngẫu nhiên với xác suất bằng nhau và ghé thăm một công viên mà con đường đó dẫn đến. Nhưng trước khi bắt đầu cuộc hành trình, anh ấy nhìn qua cửa sổ tòa nhà chọc trời của mình và thấy rằng trên mọi đoạn đường đều có một con rắn màu xanh hoặc một con rắn màu đỏ. Rắn xanh tấn công tất cả những người đi từ công viên có nhãn thấp hơn đến công viên có nhãn cao hơn, rắn đỏ tấn công tất cả những người đi từ công viên có nhãn cao hơn đến công viên thấp hơn. Vì Vito không muốn bị rắn tấn công nên anh quyết định thay đổi kế hoạch của mình bằng cách chỉ xem xét những con đường mà anh sẽ không bị rắn tấn công khi chọn một con đường ngẫu nhiên. Vì anh ấy thích đi bộ đường dài nên anh ấy sẽ không dừng lại trên hành trình của mình cho đến khi có ít nhất một con đường mà anh ấy có thể đi qua một cách an toàn.

Và khi Vito bước xuống cầu thang của tòa nhà chọc trời của mình, anh ấy hoàn toàn quên mất con đường nào là con rắn đỏ hay con rắn xanh nên anh ấy tự hỏi: Nếu trên mọi con đường đều có xác suất xuất hiện một con rắn xanh hay một con rắn đỏ bằng nhau thì vẻ đẹp kì vọng trong hành trình của tôi bắt đầu ở công viên thứ i là bao nhiêu? Vẻ đẹp của con đường là tổng vẻ đẹp của các công viên đã ghé thăm trên hành trình đó. Vẻ đẹp kì vọng của hành trình được định nghĩa là tổng các tích của vẻ đẹp của một con đường với xác suất Vito đi theo con đường đó đối với mọi con đường có thể.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ (~2 \leq n \leq 10^6~) là số công viên.
• Dòng thứ hai chứa ~n-1~ số nguyên ~p_i~ (~1 \leq p_i < i~) thể hiện đoạn đường giữa công viên thứ ~p_i~ và công viên thứ ~i~.
• Dòng thứ ba chứa ~n~ số nguyên ~v_i~ (~0 \leq v_i \leq 10^6~) là vẻ đẹp của công viên thứ ~i~.

Output

Nếu vẻ đẹp kì vọng của hành trình của Vito là ~\frac{a}{b}~ với ~a~ và ~b~ là các số nguyên thì ở dòng thứ ~i~ đưa ra ~ab^{-1} (mod \space 10^9 + 7)~ trong đó ~b^{-1}~ là nghịch đảo modulo của ~b\space (mod \space 10^9+7)~.

Scoring

1. ~n \leq 10~ (10 điểm)

2. ~n \leq 1000~ (30 điểm)

3. Trong dãy ~(p_i)~ không có giá trị nào xuất hiện quá ~2~ lần (30 điểm)

4. Không có ràng buộc gì thêm (40 điểm)

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

968750272
610352580
450521029
536458466
199219275
662760680
190972315
90277951
824219264
941840425
532552597

Explanation

• Ở ví dụ đầu tiên: vẻ đẹp kì vọng của hành trình bắt đầu từ công viên đầu tiên là ~2.5 =\frac{5}{2}=5 \times 2^{-1} = 5\times 500000004=500000006 \space (mod \space 10^9+7)~ và bắt đầu từ công viên thứ ~2~ là ~2~.
• Ở ví dụ thứ hai: xác suất tất cả rắn đều là màu đỏ là ~\frac{1}{4}~ và trong trường hợp Vito bắt đầu ở công viên ~1~ ngẫu nhiên chọn đường.