Cửa hàng Snow Crab có món bánh mì kẹp hải sản rất nổi tiếng. Mỗi loại món cho vào bánh được gán một chỉ số nguyên không âm. Nếu một chiếc bánh được kẹp các món có chỉ số ~a_1, a_2, \ldots, a_m~ thì chỉ số của bánh thành phẩm là ~a_1 \oplus a_2 \oplus \cdots \oplus a_m~, trong đó ~\oplus~ là phép xor (toán tử ^ trong C/C++).

Hôm nay bộ phận chế biến đã chuẩn bị sẵn ~n~ món theo đúng thứ tự trên băng chuyền: ~a_1, a_2, \ldots, a_n~. Cửa hàng nhận được ~k~ yêu cầu; yêu cầu thứ ~j~ cần một chiếc bánh có chỉ số nằm trong đoạn ~[u_j, v_j]~.

Bộ phận đóng gói hoạt động như sau: mỗi lần sẽ lấy một đoạn liên tiếp các món tính từ đầu phần còn lại của băng chuyền (tức là chia dãy ~a_1..a_n~ thành ~k~ đoạn liên tiếp, không rỗng, theo thứ tự), gói thành một chiếc bánh và giao cho khách. Các yêu cầu phải được đáp ứng theo đúng thứ tự ~1..k~.

Hai cách đóng gói được coi là khác nhau nếu tồn tại ít nhất một món nằm ở bánh khác nhau giữa hai cách.

Yêu cầu

Đếm số cách chia dãy ~a_1, a_2, \ldots, a_n~ thành đúng ~k~ đoạn liên tiếp không rỗng sao cho với mọi ~j = 1..k~, giá trị xor của đoạn thứ ~j~ nằm trong ~[u_j, v_j]~.

In kết quả theo mô đun ~10^9 + 7~.

Dữ liệu

• Dòng 1: hai số nguyên ~n~ và ~k~ (~1 \le n \times k \le 10^5~, ~k \le n~).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~).
• Trong ~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~u_j, v_j~ (~0 \le u_j \le v_j \le 10^9~).

Kết quả

In ra một số nguyên: số cách đóng gói thỏa mãn, lấy theo mô đun ~10^9 + 7~.

Ví dụ

Ví dụ 1

Input

7 3
1 0 1 0 1 0 1
1 1
0 0
1 1

Output

6

Giải thích

Ví dụ 1

Ta cần chia ~a_1..a_7~ thành ~3~ đoạn liên tiếp sao cho xor các đoạn lần lượt bằng ~1~, ~0~, ~1~ (do các đoạn yêu cầu đều là một giá trị cố định).

Có đúng ~6~ cách chọn hai vị trí cắt ~i < j~ (đoạn 1 là ~[1..i]~, đoạn 2 là ~[i+1..j]~, đoạn 3 là ~[j+1..7]~) thỏa mãn điều kiện, nên đáp án là ~6~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \times k \le 10^5~, ~k \le n~
• ~0 \le a_i \le 10^9~
• ~0 \le u_j \le v_j \le 10^9~
• Kết quả lấy theo mô đun ~10^9 + 7~