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\).

Input

• 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)\)

Output

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.

Scoring

• Subtask #1 (\(20\%\) số điểm): \(n,q \leq 20\).
• Subtask #2 (\(20\%\) số điểm): \(n,q \leq 5000\).
• Subtask #3 (\(20\%\) số điểm): \(n \leq 10^5, q \leq 100\).
• Subtask #4 (\(40\%\) số điểm): \(n,q \leq 10^5\).

Example

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

7
1
3
0
1