Sau bao năm vất vả học tập và giải những bài toán khó của Alice, Bob bây giờ đã là một quản lý của một công ty lớn. Một ngày đẹp trời nọ, Alice quyết định thăm Bob và cho Bob một bài toán khác để thử thách cậu.

Giả sử công ty của Bob gồm \(n\) nhân viên được đánh chỉ số từ \(1\) đến \(n\) và người thứ \(i\) có năng lực là \(a_i\). Một đội là một nhóm các nhân viên và năng lực của đội đó là tổng XOR (exclusive or) của năng lực của mọi người trong đội. Alice sẽ đưa ra tổng cộng \(q\) yêu cầu, mỗi yêu cầu thuộc một trong hai loại sau:

1. Thay đổi năng lực của nhân viên thứ \(i\) thành \(x\).
2. Đếm số cách chọn một đội mà mỗi nhân viên có chỉ số nằm trong đoạn \([l, r]\) và năng lực của đội đúng bằng \(s\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 5 \times 10^{4})\) là số lượng nhân viên trong công ty của Bob và số lượng yêu cầu của Alice.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_n\) \((1 \leq a_{i} \leq 10^{6})\) là năng lực của các nhân viên.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên \(i\) và \(x\) \((1 \leq i \leq n, 1 \leq x \leq 10^{6})\) mô tả yêu cầu loại \(1\). Số \(2\) theo sau bởi ba số nguyên \(l\), \(r\) và \(s\) \((1 \leq l \leq r \leq n\), \(1 \leq s \leq 10^{6})\) mô tả yêu cầu loại \(2\).

Output

• Đối với mỗi yêu cầu loại \(2\), in ra một số nguyên trên một dòng là phần dư của số cách chọn thỏa mãn khi chia cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\), \(a_i \leq 10^{3}\), không có yêu cầu loại \(1\) và mọi yêu cầu loại \(2\) đều có \(l = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3
1 2 3
2 1 3 3
2 1 2 3
2 1 3 1

2
1
2