Cho một dãy số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~. Đếm số cách chia dãy này thành ~k~ đoạn con liên tiếp, thỏa mãn tổng ~XOR~ đoạn thứ ~i~ ~(i \le k)~ nằm trong đoạn ~[L_i, R_i]~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^5, n * k \le 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~ ~(a_i \le 10^9)~.

• ~k~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~L_i~ và ~R_i~ là điều kiện của đoạn thứ ~i~ ~1 \le L_i \le R_i \le 10^9)~.

Output

Gồm một số nguyên duy nhất là kết quả của bài toán. Do kết quả có thể khá lớn, hãy in kết quả ~MOD~ ~10^9 + 7~.

Sample Input 1

4 2
1 2 3 4
1 4
2 10

Sample Output 1

2