Bạn được cho một cây \(N\) đỉnh và giá trị mỗi đỉnh \(val_i\) ban đầu là \(0\)

Gọi đường đi từ \(u\) đến \(v\) như sau: \(p_1,p_2,p_3...p_k\) trong đó \(p_1=u\) va \(p_k=v\) và \(p_i\) và \(p_{i+1}\) được kết nối.

Yêu cầu thực hiện 2 loại truy vấn sau:

• "1 u v x" Thêm \(x\) vào \(val_{p1}\), \(2x\) vào \(val_{p2}\), \(3x\) vào \(val_{p3}\)... , \(kx\) vào \(val_{pk}\)
• "2 u v" In tổng các giá trị của các nút trên đường đi giữa \(u\) và \(v\) theo modulo \(10^9+7\)

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên \(N\) và \(Q\) cách nhau bởi một dấu cách.
• Tiếp theo, \(N-1\) dòng chứa hai số nguyên, biểu thị các cạnh vô hướng của cây.
• Tiếp theo, \(Q\) dòng chứa một trong các loại truy vấn được mô tả ở trên.
• Lưu ý: Các nút được đánh số từ \(0\).

Dữ liệu ra

Với mỗi truy vấn loại thứ hai, in ra một số nguyên duy nhất.

Ràng buộc

• \(1 \le N,Q \le 50000\)
• \(0 \le x \lt 10^9+7\)

Input 1

3 2
0 1
1 2
1 0 2 1
2 1 2

Output 1

5