Đếm dãy con theo tổng XOR

Cho một mảng gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$.

Bạn cần trả lời $q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $l$ và $x$: hãy đếm số dãy con (subsequence) của $l$ phần tử đầu tiên $a_1,a_2,\dots ,a_l$ sao cho tổng XOR (XOR theo bit) của các phần tử trong dãy con đó bằng đúng $x$.

Một dãy con có thể chứa các phần tử không liền kề nhau, và hai dãy con được coi là khác nhau nếu chúng khác nhau về tập chỉ số được chọn. Dãy con rỗng có tổng XOR bằng $0$, và dãy con chỉ gồm một phần tử có tổng XOR bằng chính phần tử đó.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ — số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $x$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng số lượng dãy con thỏa mãn, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n,q\le {10}^5$
• $0\le a_i<2^{20}$
• $1\le l\le n$
• $0\le x<2^{20}$

Ví dụ