Cho dãy số a1, a2, …, an và q thao tác thuộc 1 trong 2 loại sau:
1 k b: gán ak=b
2 l r: Tính số lương tập con khác rỗng của tập {al,al+1,…,ar} có tổng các phần tử là số chẵn.
Dữ liệu
Dòng đầu chứa 2 số nguyên n,q.
Dòng tiếp theo chứa n số a1,a2,…,an (1<=ai<=109).
q dòng tiếp theo mỗi dòng chứa một trong hai loại thao tác :
1 k b (1<=k<=n; 1<=b<=109)
2 l r (1<=l<=r<=n)
Kết quả
Với mỗi thao tác loại 2, in ra số lượng tập con thỏa mãn (mod 109+7) trên một dòng.
Input
5 6
2 4 6 8 10
2 1 3
2 4 4
2 4 5
1 4 7
2 4 4
2 4 5
Output
7
1
3
0
1
Giới hạn:
+ 20% số test có n,q<=20.
+ 20% số test có n,q<=5000.
+ 20% số test có n<=105, q<=100.
+ 40% số test có n,q<=105.