Alice đang nghiên cứu một hệ thống phân tích dữ liệu gồm một dãy ~N~ số nguyên ~A_1,A_2,\dots,A_N~. Trong quá trình phân tích, giá trị của các phần tử trong dãy có thể bị thay đổi. 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~ ~v~, trong đó ~1 \le i \le N~ và ~0 \le v \le 10^9~, có nghĩa là số thứ ~i~ của dãy bị thay đổi thành ~v~.

2. Loại 2 có dạng: 2 ~l~ ~r~ ~k~, trong đó ~1 \le l \le r \le N~ và ~1 \le k \le 5~, có nghĩa là cần tính giá trị ~\displaystyle \sum_{i=l}^{r}\sum_{j=l}^{r}(A_i+A_j)^k~.

Yêu cầu: Cho dãy số ~A~ ban đầu và ~Q~ sự kiện, với mỗi sự kiện loại 2 hãy đưa ra kết quả tương ứng.

Input

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

• Dòng thứ hai chứa ~N~ số nguyên ~A_1,A_2,\dots,A_N~ ~(0 \le A_i \le 10^9)~.

• Tiếp theo là ~Q~ dòng, mỗi dòng mô tả loại sự kiện xảy ra.

Output

Gồm một số dòng, mỗi dòng chứa một số nguyên duy nhất tương ứng với sự kiện loại 2 xảy ra. Vì kết quả có thể rất lớn nên chỉ cần đưa ra kết quả chia lấy dư cho ~10^9+7~.

Scoring

Sample Input 1

3 3
1 2 3
2 1 3 1
1 2 0
2 1 2 2

Sample Output 1

36
6