Truy vấn dãy số

Cho một dãy số có \(N\) phần tử. Bạn cần xử lý \(M\) truy vấn thuộc 4 loại sau:

• \(1\;L\;R\;x\): Cộng thêm \(x\) đơn vị vào tất cả phần tử từ vị trí \(L\) đến \(R\).
• \(2\;L\;R\;x\): Nhân tất cả phần tử từ \(L\) đến \(R\) với \(x\).
• \(3\;L\;R\;x\): Gán tất cả phần tử từ \(L\) đến \(R\) bằng \(x\).
• \(4\;L\;R\): Tính tổng các phần tử từ \(L\) đến \(R\), lấy dư với \(10^9 + 7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\), \(M\) — số phần tử và số truy vấn (\(1 \le N, M \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên ban đầu (\(1 \le A_i \le 10^9\)).
• Mỗi dòng tiếp theo là một truy vấn theo một trong bốn dạng đã mô tả.

Output

Với mỗi truy vấn loại 4, in ra tổng các phần tử từ \(L\) đến \(R\) (modulo \(10^9 + 7\)), mỗi kết quả trên một dòng.

Scoring

• Có \(30\%\) số điểm ứng với \(N, M \le 10^3\).
• \(70\%\) số điểm còn lại ứng với \(N, M \le 10^5\).

Input

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

Output

43