Tèo đang quản lý một chuỗi cửa hàng bán bánh mỳ. Ban đầu chuỗi có \(N\) cửa hàng, cửa hàng thứ \(i\) có doanh thu là \(A_i\). Để đánh giá hiệu quả kinh doanh và chuẩn bị cho các đợt kiểm toán doanh thu, Tèo cần quản lý biến động doanh thu qua các sự kiện. Cụ thể, có \(Q\) yêu cầu thuộc ba loại như sau:

• 1 l r v: Do sự kiện khuyến mãi cực lớn, doanh thu của tất cả các cửa hàng từ chỉ số \(l\) đến chỉ số \(r\) được nhân lên \(v\) lần.
• 2 l r v: Tèo trợ giá hỗ trợ thêm cho tất cả các cửa hàng từ chỉ số \(l\) đến chỉ số \(r\) một lượng doanh thu là \(v\).
• 3 l r: Cơ quan thuế yêu cầu Tèo báo cáo tổng doanh thu của tất cả các cửa hàng trong khoảng từ chỉ số \(l\) đến chỉ số \(r\).

Vì doanh thu có thể rất lớn, tất cả các phép tính và kết quả báo cáo cần được thực hiện theo modulo \(10^9 + 7\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một yêu cầu thuộc một trong ba định dạng trên (\(1 \le l \le r \le N\), \(0 \le v \le 10^9\)).

Định dạng đầu ra

• Với mỗi yêu cầu loại 3, in ra tổng doanh thu trên một dòng riêng biệt theo modulo \(10^9 + 7\).

Ví dụ

Input:

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

Output:

9
23