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 món (nguyên liệu) được gán một chỉ số nguyên không âm ~a_1, a_2, \dots~. Nếu một chiếc bánh được kẹp từ các món có chỉ số ~a_1, a_2, \dots, 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++).

Trong ngày hôm nay, bếp chuẩn bị sẵn ~n~ món theo đúng thứ tự trên băng chuyền: ~a_1, a_2, \dots, a_n~ và phải dùng hết trong ngày. Cửa hàng nhận được ~k~ yêu cầu, yêu cầu thứ ~i~ cần một chiếc bánh có chỉ số nằm trong đoạn ~[u_i, v_i]~. Các yêu cầu được phục vụ theo đúng thứ tự gửi đến.

Khi đóng gói, hệ thống sẽ luôn lấy ra một dãy các món liên tiếp (theo thứ tự xuất hiện trên băng chuyền, từ phần còn lại ở đầu), kẹp thành một chiếc bánh cho yêu cầu hiện tại, rồi tiếp tục với yêu cầu kế tiếp. Nói cách khác, ta phải chia dãy ~a_1..a_n~ thành đúng ~k~ đoạn con liên tiếp, không rỗng, theo thứ tự.

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 thuộc về một chiếc bánh trong cách thứ nhất nhưng thuộc về chiếc bánh khác trong cách thứ hai (tương đương: vị trí các điểm cắt khác nhau).

Yêu cầu

Tính số cách chia dãy ~a_1, a_2, \dots, a_n~ thành đúng ~k~ đoạn liên tiếp không rỗng sao cho với mọi ~i~:

• XOR của đoạn thứ ~i~ nằm trong ~[u_i, v_i]~.

Kết quả lấy theo mô đun ~10^9 + 7~.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~n~ và ~k~ (~1 \le n \times k \le 10^5~, ~k \le n~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~).
• Trong ~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số ~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 khác nhau có thể thực hiệ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

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

• ~1 \le n \times k \le 10^5~, ~k \le n~
• ~0 \le a_i \le 10^9~
• ~0 \le u_i \le v_i \le 10^9~
• Phải chia thành đúng ~k~ đoạn liên tiếp không rỗng, dùng hết ~n~ món.