Bạn được cho 1 xâu $a$ gồm $n$ ký tự chỉ gồm các ký tự như &, |, ^ (tương đương với phép toán AND, OR, XOR). Bạn phải thực hiện $q$ truy vấn:

• $1$ $k$ $x$: Cập nhật ký tự thứ $k$ trong xâu $a$ thành $x$ ($1\le k\le n$, $x$ thuộc 1 trong 3 loại ký tự như trên)
• $2$ $l$ $r$ $k$ $u$ $v$: Tính độ đẹp của xâu trong đoạn $[l,r]$ với các giá trị $k,u,v$ ($1\le l\le r\le n,1\le k\le 20,0\le u\le v<2^k$)

huyhau6a2 định nghĩa độ đẹp của một xâu ký tự $a$ độ dài $x$ với các giá trị $k,u,v$ như sau: Là số lượng dãy $b$ thỏa mãn ($0\le b_i<2^k$):

Chú ý: Thứ tự thực hiện tính toán theo các ký tự của xâu $a$ được thực hiện từ trái sang phải

VD: Xâu |^ với $k=1,u=1,v=1$ thì có các khả năng như sau:

• 0|0^0=0
• 0|0^1=1
• 0|1^0=1
• 0|1^1=0
• 1|0^0=1
• 1|0^1=0
• 1|1^0=1
• 1|1^1=0

Theo như kết quả ở trên, có 4 kết quả thỏa mãn. Vậy độ đẹp của xâu |^ với $k=1,u=1,v=1$ là $4$

Nhiệm vụ của bạn là phải tính toán các kết quả của truy vấn 2. Vì kết quả rất lớn nên hãy xuất kết quả $mod\ 10^9+7$

3 4
&|^
2 2 3 1 1 1
1 3 |
2 2 3 1 0 1
2 1 3 2 2 2

4
8
39