Giải bài trực tuyến

Như các bạn biết (hoặc có thể sắp biết) thì yenthanh132 rất thích số 7. T7 cũng là một nickname khác của yenthanh132. Nhưng ta sẽ nói về chuyện đó sau... Hôm nay yenthanh132 có một bài toán cho các bạn và có liên quan tới số 7.

yenthanh132 sắp n hòn đá thành một hàng thẳng, mỗi hòn đá có một mức năng lượng là a_i, biết rằng mức năng lượng của một hòn đá là một số nguyên dương. Các hòn đá được đánh số từ trái sang phải lần lượt các số từ 0 đến n - 1 (n ≤ 10⁵). Sau đó yenthanh132 yêu cầu các bạn trả lời các truy vấn sau:

• 1 i : Xóa hòn đá ở có số thứ tự i (0 ≤ i ≤ n-1). Sau đó các hòn đá bên phải hòn đá bị xóa sẽ dịch sang trái 1 đơn vị, và tất nhiên số thứ tự của mỗi hòn đá cũng như giá trị n (tổng số hòn đá) sẽ giảm đi 1.
• 2 i v : Thay đổi mức năng lượng của hòn đá có số thứ tự i thành v. (1 ≤ v ≤ 10⁹; 0 ≤ i ≤ n-1)
• 3 k : Tính giá trị năng lượng kết hợp của các hòn đá có số thứ tự là 7*t + k (với 0 ≤ t ≤ (n-k-1) div 7). Nói cách khác đó là các hòn đá có số thứ tự i sao cho i mod 7 = k (0 ≤ i ≤ n-1).

Biết rằng giá trị năng lượng kết hợp của các hòn đá bằng tích mức năng lượng của các hòn đá đó. Do giá trị này có thể rất lớn nên yenthanh132 chỉ yêu cầu các bạn tìm phần dư của giá trị này sau khi chia cho 1.000.000.007 (tức 10⁹ + 7).

Trong mọi thời điểm, số lượng hòn đá còn lại luôn lớn hơn hoặc bằng 7.

Dữ liệu vào

• Dòng đầu chứa 2 số nguyên dương n, m lần lượt là số lượng hòn đá ban đầu, số truy vấn cần thực hiện.
• Dòng tiếp theo chứa n số nguyên dương, a_i là mức năng lượng của hòn đá i (i từ 0 đến n - 1)
• m dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong 3 loại đã nêu ở trên.

Dữ liệu ra

• Với mỗi truy vấn 3, in ra kết quả trên một dòng. Kết quả ở đây đã được mod 1.000.000.007.

Giới hạn

• 25% số test có n, m ≤ 1000.
• Các test còn lại có n, m ≤ 10⁵.
• 1 ≤ a_i ≤ 10⁹ (với i từ 0 đến n - 1)

Ví dụ

Input:
10 5
3 2 1 6 7 5 2 1 8 10
3 2
1 0
3 0
2 7 7
3 0

Output:
10
16
14