Cho một cây có ~n~ đỉnh và ~n - 1~ cạnh. Một đỉnh ~i~ khác đỉnh gốc có cha trên cây là đỉnh ~p_i~, còn nếu ~i~ là gốc thì ~p_i = 0~. Mỗi đỉnh trên cây còn có một giá trị gọi là giá trị của đỉnh, ban đầu giá trị của tất cả các đỉnh đều bằng ~1~.

Cho một dãy ~a~ là thứ tự xét các đỉnh, tại mỗi đỉnh ~u~ được xét cần thực hiện biển đổi sau:

• Với mỗi đỉnh ~v~ thuộc đường đi từ đỉnh gốc đến đỉnh cha của đỉnh ~u~, tăng giá trị của đỉnh ~v~ một lượng bằng với giá trị đỉnh ~u~.

Với mỗi đỉnh trên cây, hãy cho biết giá trị của đỉnh đó tính đến thời điểm nó được thăm là bao nhiêu, in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ - số đỉnh trên cây ~(1 \le n \leq 10^5)~.

• Dòng thứ hai chứa ~n~ số ~p_1, p_2,..., p_n~. ~(1 \le p_i \le n)~

• Dòng thứ ba chứa ~n~ số ~a_1, a_2,..., a_n~. ~(1 \le a_i \le n)~

Output

• In ra ~n~ dòng, dòng thứ ~i~ chứa một số duy nhất là giá trị đỉnh ~i~ tính đến thời điểm đỉnh ~i~ được xét chia lấy dư cho ~10^9 + 7~.

Subtask

• ~20\%~ số test có ~n \leq 1000~.
• ~80\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

6
2 3 0 5 3 5
1 4 6 5 2 3

Sample Output 1

1 2 9 1 3 1 

Note

• Giá trị ban đầu của các đỉnh: ~[1, 1, 1, 1, 1, 1]~
• ~1~: ~[1, 2, 2, 1, 1, 1]~
• ~4~: ~[1, 2, 3, 1, 2, 1]~
• ~6~: ~[1, 2, 4, 1, 3, 1]~
• ~5~: ~[1, 2, 7, 1, 3, 1]~
• ~2~: ~[1, 2, 9, 1, 3, 1]~
• ~3~: ~[1, 2, 9, 1, 3, 1]~