Xét một tập ~S~ gồm ~k~ phần tử, kí hiệu là ~S_k=\{s_1,s_2,\dots,s_k\}~, định nghĩa ~f(S_k)=s_1\cdot s_2 \cdot \ldots \cdot s_k~ là giá trị của tập ~S_k~.

Cho một dãy số gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~. Với một đoạn ~a[l..r]~, gọi ~g(l,r)=\sum_{S_k \subset \{a_l,a_{l+1},\ldots,a_r\}}f(S_k)~ là giá trị của đoạn con này. Ta sẽ lần lượt thực hiện ~q~ truy vấn trên dãy số đã cho:

• 1 l r: Tính ~g(l, r)~ - tổng giá trị của các tập con thuộc tập hợp ~\{a_l, a_{l + 1}, \ldots, a_r\}~.

• 2 i x: Thay đổi ~a_i = x~.

Yêu cầu: Với mỗi truy vấn loại 1, hãy in ra ~g(l, r)~ trong truy vấn tương ứng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ (~1 \le n \le 10^5, 1 \le k \le 20~).

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

• Dòng thứ ba chứa số nguyên dương ~q~ (~1 \le q \le 10^5~).

• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong hai dạng nêu trên.

• Trong các truy vấn loại ~1~, ~1\le l\le r\le n~; trong các truy vấn loại 2, ~1\le i \le n~ và ~1\le x \le 10^9~.

Output

• In ra nhiều dòng, mỗi dòng là đáp án cho truy vấn loại ~1~ tương ứng trong dữ liệu đầu vào. Vì đáp án có thể rất lớn, hãy in ra số dư khi chia cho ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20~ điểm): ~n, q \le 1000~

• Subtask ~2~ (~30~ điểm): ~a_i, x \le 2~

• Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

5 2
3 10 3 5 10
4
1 1 4
2 3 4
2 2 6
1 2 4

Sample Output 1

149
74

Notes

Ở test ví dụ trên:

• Ở truy vấn thứ ~1~, ta được yêu cầu tính ~g(1, 4)~. Đáp án của truy vấn này là ~3 \cdot 10 + 3 \cdot 3 + 3 \cdot 5 + 10 \cdot 3 + 10 \cdot 5 + 3 \cdot 5 = 149~.

• Ở truy vấn thứ ~2~, ta thực hiện thay đổi ~a_3 = 4~. Lúc này, ~a = [3, 10, 4, 5, 10]~.

• Ở truy vấn thứ ~3~, ta thực hiện thay đổi ~a_2 = 6~. Lúc này, ~a = [3, 6, 4, 5, 10]~.

• Ở truy vấn thứ ~4~, ta được yêu cầu tính ~g(2, 4)~. Đáp án của truy vấn này là ~6 \cdot 4 + 6 \cdot 5 + 4 \cdot 5 = 74~.