Vito sống trong 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 nối bởi ~n - 1~ con đường sao cho giữa mọi cặp công viên đều có một đường đi. Mỗi công viên có một giá trị đẹp; giá trị đẹ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 sau: sau khi tới một công viên, anh chọn một con đường với xác suất bằng nhau và đi tới công viên mà con đường đó dẫn tới. Nhưng trước khi khởi hành, anh nhìn qua cửa sổ toà nhà cao tầng của mình và thấy rằng trên mỗi con đường có một con rắn xanh hoặc một con rắn đỏ. Rắn xanh tấn công tất cả những người đi từ công viên có nhãn nhỏ hơn sang công viên có nhãn lớn hơn, còn rắn đỏ tấn công tất cả những người đi từ công viên có nhãn lớn hơn sang công viên có nhãn nhỏ hơn.

Vì Vito không muốn bị rắn tấn công, anh quyết định đổi kế hoạch: khi chọn một con đường ngẫu nhiên, anh chỉ xét những con đường mà anh sẽ không bị rắn tấn công. Vì anh thích đi bộ đường dài, anh sẽ không dừng lại cho tới khi không còn con đường nào có thể đi qua an toàn.

Và khi Vito đi xuống cầu thang toà nhà, anh hoàn toàn quên mất con đường nào có rắn đỏ hay rắn xanh, nên anh tự hỏi: nếu trên mỗi con đường xác suất có rắn xanh và rắn đỏ là bằng nhau, thì giá trị đẹp kỳ vọng của chuyến đi bắt đầu từ công viên thứ ~i~ là bao nhiêu?

Giá trị đẹp của một đường đi là tổng giá trị đẹp của các công viên được thăm trên đường đi đó. Giá trị đẹp kỳ vọng của chuyến đi được định nghĩa là tổng, trên mọi đường đi có thể, của tích giữa giá trị đẹp của đường đi đó và xác suất Vito đi theo đường đi đó.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số công viên.
• Dòng thứ hai chứa ~n - 1~ số nguyên ~p_i~ (~1 \le p_i < i~), cho biết có một con đường giữa công viên thứ ~(i+1)~ và công viên thứ ~p_i~.
• Dòng thứ ba chứa ~n~ số nguyên ~v_i~ — giá trị đẹp của công viên thứ ~i~.

Kết quả

Nếu giá trị đẹp kỳ vọng của chuyến đi bắt đầu tại công viên thứ ~i~ là ~\dfrac{a}{b}~ với ~a~, ~b~ nguyên, thì ở dòng thứ ~i~ hãy in ra ~a \cdot b^{-1} \pmod{10^9 + 7}~, trong đó ~b^{-1}~ là nghịch đảo modulo của ~b~ theo modulo ~10^9 + 7~.

Ví dụ

Đầu vào:

2
1
2 1

Đầu ra:

500000006
2

Giải thích: Cây chỉ gồm hai công viên nối với nhau bởi một con đường, với ~v_1 = 2~ và ~v_2 = 1~.

Bắt đầu từ công viên ~1~: đi từ ~1~ sang ~2~ là đi từ nhãn nhỏ sang nhãn lớn nên bị rắn xanh tấn công. Vậy Vito chỉ đi được nếu con rắn là đỏ (xác suất ~\tfrac{1}{2}~), khi đó anh sang công viên ~2~ rồi không đi tiếp được nữa, thu ~2 + 1 = 3~. Nếu con rắn là xanh thì anh không đi đâu được, chỉ thu ~2~. Kỳ vọng là ~\dfrac{3 + 2}{2} = \dfrac{5}{2}~, và ~5 \cdot 2^{-1} \equiv 500000006 \pmod{10^9+7}~.

Bắt đầu từ công viên ~2~: tương tự, kỳ vọng là ~\dfrac{3 + 1}{2} = 2~.

Giới hạn

• ~2 \le n \le 10^6~
• ~1 \le p_i < i~
• ~0 \le v_i \le 10^6~

Điểm của một subtask bằng điểm nhỏ nhất đạt được trên một test nào đó thuộc subtask đó. Lưu ý rằng ~n~ có thể lên tới ~10^6~ và cây có thể là một đường thẳng, nên hãy tránh đệ quy sâu khi duyệt cây.