Cho dãy số a₁,a₂,...,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₁,k₂,...,k_m} khác rỗng của tập {l,l+1,...,r} sao cho a_k1+a_k2+...+a_km 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⁹+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₁,a₂,...,a_n(1≤ a_i ≤10⁹).
• 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 ≤ 10⁹)
  • 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 10⁹+7) trên một dòng.

Giới hạn:

• 20% số test có n, q ≤ 20.
• 20% số test có n, q ≤ 5000.
• 20% số test có n ≤ 10⁵, q ≤ 100.
• 40% số test có n, q ≤ 10⁵.