Tổng tích dãy con


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Với dãy $B$, ta liệt kê các dãy con của $B$. Với mỗi dãy con, ta tính tích các phần tử. Tổng của các tích phần tử khi xét tất cả dãy con được gọi là tổng tích của dãy $B$.

Nhắc lại, dãy con của dãy có được bằng việc xóa đi một vài phần tử (hoặc không xóa, hoặc xóa hết) mà không làm thay đổi thứ tự các phần tử còn lại.

Tương tự, ta có $TC(B)$ là tổng tích các dãy con có độ dài chẵn của $B$ và $TL(B)$ là tổng tích các dãy con có độ dài lẻ của $B$.

Cho dãy $a_1,a_2,...,a_N$. Có $Q$ truy vấn, mỗi truy vấn thuộc một trong ba loại:

  • 1 x y: gán $a_x \gets y$;
  • 2 l r: tìm giá trị của $TC(a_l, a_{l+1}, ..., a_r)$;
  • 3 l r: tìm giá trị của $TL(a_l, a_{l+1}, ..., a_r)$.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N,Q \ (1\le N,Q \le 5\times 10^4)$;
  • Dòng tiếp theo chứa $N$ số nguyên $a_i \ (1\le a_i \le 10^9)$;
  • $Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l,r,K$ $(1\le y \le 10^9; 1\le l \le r \le N)$.

Kết quả

  • Với mỗi truy vấn loại 2 và 3, in kết quả sau khi chia lấy dư cho $10^9+7$ trên một dòng. Nếu không tồn tại kết quả, in ra $-1$.

Ví dụ

Ví dụ 1

input

5 3
1 1 2 1 2
1 2 1
2 1 3
3 1 3

output

6
6

Comments

There are no comments at the moment.