An rất thích làm toán, đặc biệt các bài toán số học. Có bài toán như sau: Cho dãy số nguyên ~a_1,a_2,...,a_n~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~, để tính tổng các số trong đoạn ~[i, j]~ cho trước thì ta tính ~a_i + a_{i+1} + ... + a_j~. Ví dụ cho dãy số ~2,5,-3,7,-9~ thì tổng đoạn ~[2, 4]~ là ~5 - 3 + 7 = 9~. Biết các bạn lớp 10I năm nay học toán rất tốt nên An đã mở rộng bài toán như sau:

Có ~Q~ truy vấn, mỗi truy vấn có hai loại:

• ~1~ ~x~ ~y~: gắn lại ~a_x = y~.
• ~2~ ~l~ ~r~ ~k~: tính tổng ~(a_u + a_{u+1} + ... + a_v)^k~, với tất cả ~u, v~: ~l \leq u \leq v \leq r~ và ~k = 1~ hoặc ~k = 2~.

Yêu cầu: Cho dãy số nguyên ~a_1,a_2,...,a_n~ với ~Q~ truy vấn như trên, các bạn hãy viết chương trình giải bài toán trên.

Input

Vào từ file văn bản KSUM.INP:

• Dòng đầu tiên ghi số nguyên dương ~n, Q~ (~1 \leq n,Q \leq 5*10^5~);
• Dòng tiếp theo ghi dãy số nguyên dương ~a_1,a_2,...,a_n~ (~1 \leq a_i \leq 10^6~);
• ~Q~ dòng tiếp theo mỗi dòng ghi lần lượt mỗi trong hai truy vấn sau:
  • ~1 ~ ~x ~ ~y ~: ~1 \leq x \leq n, 1 \leq y \leq 10^9~;
  • ~2 ~ ~l ~ ~r ~ ~k~ : ~1 \leq l \leq r \leq n,~ ~k = 1~ hoặc ~k = 2~.

Lưu ý: Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra file văn bản KSUM.OUT với mỗi truy vấn loại 2 (~2~ ~l~ ~r~ ~k~) in kết quả khi chia lấy dư cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(17\%)~: ~n,Q \leq 500~.
• Subtask ~2~ ~(17\%)~: ~n,Q \leq 5000~.
• Subtask ~3~ ~(21\%)~: Không có truy vấn loại 1, ~a_i = 1~.
• Subtask ~4~ ~(22\%)~: ~k = 1, n \leq 5*10^5~.
• Subtask ~5~ ~(23\%)~: Không có ràng buộc gì thêm.

Example input 1

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

Example output 1

20
16
56

Example input 2

2 4
1 2
2 1 2 2
1 1 2
2 1 2 1
2 1 2 2

Example output 2

14
8
24