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~ ~(1 \le n \leq 10^{5})~. 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 \leq~ i ~\leq 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 \leq v \leq 10^{9}~; ~0 \leq i \leq 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 \times t + k~ (với ~0 \leq t \leq \frac{n-k-1}{7}~). Nói cách khác đó là các hòn đá có số thứ tự ~i~ sao cho ~i \bmod 7 = k~ ~(0 \leq i \leq 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 ~1000000007~ (tức ~10^{9} + 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~.

Input

• 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.

Output

• 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 ~10^9 + 7~.

Giới hạn

• ~25\%~ số test có ~n~, ~m \leq 1000~.
• Các test còn lại có ~n~, ~m \leq 10^{5}~.
• ~1 \leq a_{i} \leq 10^{9}~ (~i~ từ ~0~ đến ~n - 1)~.

Sample Input

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

Sample Output

10
16
14