Quân đội của đại tướng Trần có ~n~ đơn vị được đánh số từ ~1~ đến ~n~. Đơn vị ~1~ có cấp bậc cao nhất, còn các đơn vị ~i~ với ~2 \le i \le n~ sẽ nhận đơn vị ~p_i~ làm cấp trên trực tiếp. Đảm bảo rằng, cách sắp xếp cấp bậc này được dựa trên mô hình cây. Nói cách khác, mô hình quân đội là một cây có gốc ở đỉnh ~1~. Ngoài ra, đơn vị thứ ~i~ có quân số là ~a_i~.

Một cách triệu tập quân đội với đơn vị ~u~ là chỉ huy là việc chọn một dãy các đơn vị ~x_1, x_2, \dots, x_k~, mỗi đơn vị lấy duy nhất một binh sĩ, sao cho ~x_1 = u~ và ~p_{x_{i+1}} = x_i~ với ~1 \le i \le k - 1~.

Gọi ~S(u)~ là số cách triệu tập quân đội với ~u~ là chỉ huy.

Để kiểm tra sự linh hoạt của hệ thống quân đội, đại tướng Trần cần bạn thiết kế một chương trình thực hiện một dãy các thao tác sau:

• Thay đổi quân số của một đơn vị bất kỳ.

• Chọn một đơn vị ~u~ bất kỳ, tính ~S(u)~.

Yêu cầu: Hãy thực hiện các yêu cầu trên của đại tướng để nhận được phần thưởng hậu hĩnh.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~) — số đơn vị và số yêu cầu của đại tướng Trần.

• Dòng thứ hai gồm ~n - 1~ số nguyên dương ~p_2, p_3, \dots, p_n~ (~p_i \lt i~) — cấp trên trực tiếp của đơn vị ~i~.

• Dòng thứ ba gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) — quân số của đơn vị ~i~.

• ~q~ dòng cuối cùng, mỗi dòng là một truy vấn thuộc một trong hai dạng:

  • ~1~ ~u~ ~x~ (~1 \le u \le n, 1 \le x \le 10^9~): Gán ~a_u = x~.

  • ~2~ ~u~ (~1 \le u \le n~): Tính ~S(u)~.

Output

• Với mỗi truy vấn loại ~2~, in ra một số nguyên trên một dòng là kết quả của truy vấn, lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

4 3
1 2 2
1 1 2 2
2 2
1 2 2
2 2

Sample Output 1

5
10

Notes

• Ta có dãy ban đầu ~a = [1,1,2,2]~. Định nghĩa ~x_y~ là binh sĩ thứ ~y~ ở đơn vị ~x~.

• Khi ~a_2 = 1~ thì ~S(2) = 5~, gồm các cách chọn sau: ~[2_1]~, ~[2_1,3_1]~, ~[2_1,3_2]~, ~[2_1,4_1]~, ~[2_1,4_2]~.

• Sau khi cập nhật ~a_2 = 2~, ta có thêm ~5~ cách chọn nữa, mỗi cách đều chọn binh sĩ ~2_2~.