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\)

Input

• Dòng đầu tiên ghi số nguyên dương \(n, Q\) \((1 \leq n,Q \leq 5 \cdot 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ột 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\)
• Các số trên một dòng cách nhau dấu cách

Output

• 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\)

Example

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

20
16
56

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

14
8
24

Scoring

• Subtask \(1\) \((1.05\) điểm): \(n, Q \leq 500\)
• Subtask \(2\) \((1.05\) điểm): \(n, Q \leq 5000\)
• Subtask \(3\) \((1.40\) điểm): Không có truy vấn loại \(1\), \(a_i = 1\)
• Subtask \(4\) \((1.75\) điểm): \(k = 1, n \leq 5 \cdot 10^5\)
• Subtask \(5\) \((1.75\) điểm): Không có ràng buộc gì thêm