Cho dãy số ~a_1, a_2, …, a_n~ và ~q~ thao tác thuộc 1 trong 2 loại sau:

1 k b: gán ~a_k=b~

2 l r: Tính số lương tập con ~\{k_1, k_2, ..., k_m\}~ khác rỗng của tập ~\{l,l+1,…,r\}~ sao cho ~a_{k_1} + a_{k_2} + ... + a_{k_m}~ là số chẵn.

Yêu cầu: Với thao tác loại 2, hãy in ra số dư của kết quả khi chia cho ~10^9+7~.

Dữ liệu

• Dòng đầu chứa 2 số nguyên ~n,q~.

• Dòng tiếp theo chứa ~n~ số ~a_1,a_2,…,a_n (1\leq a_i \leq 10^9)~.

• ~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 \leq k \leq n; 1 \leq b \leq 10^9)~
  • 2 l r ~(1\leq l \leq r \leq 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 \ 10^9+7)~ trên một dòng.

Ví dụ

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 \leq 20~.
• 20% số test có ~n,q \leq 5000~.
• 20% số test có ~n \leq 10^5, q \leq 100~.
• 40% số test có ~n,q \leq 10^5~.