Alice đang xây dựng một hệ thống được đặc trưng bằng một dãy gồm ~n~ số nguyên dương ~(a_1, a_2, \dots, a_n)~. Với hai chỉ số ~1 \le L < R \le n~, Alice định nghĩa độ ổn định đoạn ~[L, R]~ của hệ thống bằng tổng tất cả tích các cặp số trong đoạn, cụ thể: ~S(L, R) = \sum_{L \le i < j \le R} a_i \times a_j~.

Ví dụ, dãy ~(2, 1, 3, 5)~, ta có ~S(1, 2) = 2 \times 1 = 2~; ~S(2, 4) = 1 \times 3 + 1 \times 5 + 3 \times 5 = 23~.

Trong quá trình vận hành hệ thống, một số đặc trưng bị thay đổi và Alice cần tính độ ổn định của một số đoạn. Cụ thể, sẽ có ~q~ sự kiện lần lượt xảy ra, mỗi sự kiện thuộc một trong hai loại sau: 1) Loại 1 có dạng: ~1 \ i \ x~, trong đó ~1 \le i \le n~ và ~1 \le x \le 10^6~, có nghĩa là số thứ ~i~ của dãy bị thay đổi thành ~x~. 2) Loại 2 có dạng: ~2 \ L \ R~, trong đó ~1 \le L < R \le n~, có nghĩa là cần tính độ ổn định đoạn ~[L, R]~ của hệ thống.

Yêu cầu: Cho dãy ~(a_1, a_2, \dots, a_n)~ và ~q~ sự kiện, với mỗi sự kiện loại 2 hãy đưa ra độ ổn định của đoạn cần tính.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~2 \le n, q \le 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \le 10^6~).
• Tiếp theo là ~q~ dòng, mỗi dòng chứa ba số ~1 \ i \ x~ hoặc ~2 \ L \ R~ mô tả dạng sự kiện xảy ra.

Output

• Ghi ra gồm một số dòng, mỗi dòng chứa một số là độ ổn định cần tính tương ứng với sự kiện loại 2 xảy ra. Vì giá trị này có thể rất lớn nên chỉ cần đưa ra giá trị ~S(L, R) \pmod{10^9 + 7}~, trong đó phép toán ~%~ là phép toán chia lấy dư.

Subtasks

• 40% số test thỏa mãn: ~n, q \le 200~.
• 30% số test khác thỏa mãn: ~a_i \le 10^3~ và cả ~q~ sự kiện đều là thao tác loại 2.
• 30% số test còn lại không có ràng buộc nào thêm.

Sample Input 1

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

Sample Output 1

2
23
23