C11SEVEN - Dãy số và số 7

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 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 ≤ 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 9 ; 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 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.

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 5 .
  • 1 ≤ a i ≤ 10 9 (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

  • Người up: yenthanh132
  • Nguồn bài: Lê Yên Thanh