Thay đổi trên cây (On Changing Tree)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu giá trị mọi đỉnh bằng 0. Truy vấn loại 1 trên đỉnh $v$ cộng $x-i\cdot k$ cho mỗi hậu duệ ở khoảng cách $i$. Truy vấn loại 2 hỏi giá trị hiện tại tại một đỉnh modulo $10^9+7$.

Dữ liệu vào

Dòng đầu chứa $n$. Dòng hai chứa $p_2,\ldots,p_n$. Dòng tiếp theo chứa $q$, sau đó là các truy vấn 1 v x k hoặc 2 v.

Kết quả

Với mỗi truy vấn loại 2, in giá trị tại đỉnh modulo $1000000007$.

Subtask

Subtask 1 (20%)

• Kích thước cây và số thao tác không vượt 20.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• Kích thước cây và số thao tác không vượt 2000.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le3\cdot10^5$, $0\le x,k<10^9+7$.

Ví dụ

Input

1

9
2 1
1 1 581999284 308872843
1 1 974853058 641941689
1 1 471382685 727846723
2 1
1 1 290788170 687681328
2 1
1 1 780587910 592803148
2 1

Output

0
28235013
319023183
99611086

Giải thích

Ví dụ được xử lý đúng theo thứ tự các thao tác. Các truy vấn chỉ quan sát trạng thái hiện tại sau toàn bộ cập nhật đứng trước chúng; kết quả in ra tương ứng với định nghĩa ở phần Đề bài.