Cộng cây

Một khu rừng cổ xưa được quản lý bởi các nhà pháp sư. Khu rừng này bao gồm \(n\) cây, mỗi cây được xem là một đỉnh trong một cây thần linh khổng lồ. Ban đầu, mỗi đỉnh đều có năng lượng bằng \(0\). Nhiệm vụ của các pháp sư là sử dụng phép thuật để tăng cường sức mạnh cho các đỉnh và kiểm tra sự phân phối năng lượng trên các con đường trong cây.

Mỗi ngày, các pháp sư sẽ thực hiện một trong hai loại phép thuật sau:

• Loại 1: Gọi \(d(i)\) là đỉnh thứ \(i\) khi đi trên đường đi ngắn nhất từ \(u\) đến \(v\). Họ sẽ truyền thêm năng lượng cho các đỉnh trên đường đi, theo quy tắc \(a(d(i)) += i \times x\).
• Loại 2: Họ kiểm tra tổng năng lượng của tất cả các đỉnh trên con đường ngắn nhất giữa hai đỉnh \(u\) và \(v\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 10^5)\) -- số đỉnh của cây và số lượng truy vấn.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) -- biểu thị một cạnh nối giữa hai đỉnh \(a\) và \(b\).

• \(q\) dòng cuối cùng mô tả các truy vấn, mỗi truy vấn có dạng:

• 1 u v x: Thực hiện phép thuật loại 1.

• 2 u v: Thực hiện phép thuật loại 2.

Ràng buộc: \(1 \le u, v \le n\) , \(1 \le x \le 10^6\).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất thể hiện tổng năng lượng \(mod\) \((10^9 + 7)\).

Example

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

10
18

Scoring

• Subtask 1 (30% số điểm): \(n, q \leq 1000\).
• Subtask 2 (30% số điểm): Cây có dạng đường thẳng.
• Subtask 3 (40% số điểm): Không có ràng buộc thêm.