Phép toán OR

Nội dung chính trong tiết học Tin học trên lớp của Nam ngày hôm nay là về phép toán OR. Phép toán OR (có kí hiệu là $|$) được định nghĩa như sau: Kết quả của phép toán OR giữa $2$ số nguyên không âm $x$ và $y$ là một số nguyên không âm $z$ trong đó bit thứ $i$ trong biểu diễn nhị phân của $z$ sẽ là $0$ khi và chỉ khi bit thứ $i$ trong biểu diễn nhị phân của $x$ và $y$ đồng thời bằng $0$, ngược lại bit thứ $i$ trong biểu diễn nhị phân của $z$ là $1$.

Ví dụ, $x=12$ có biểu diễn nhị phân là $1100$, $y=5$ có biểu diễn nhị phân là $0101$, khi đó $x\mid y$ có biểu diễn nhị phân là $1101$, tức giá trị $13$ trong hệ cơ số thập phân.

Phép toán OR có tính chất giao hoán và kết hợp: $x\mid y=y\mid x$ và $x\mid (y\mid z)=(x\mid y)\mid z$.

Để ôn tập nội dung đã học, thầy giáo ra cho cả lớp bài tập về nhà như sau: Cho $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ và ba số nguyên $k,L,R$. Hãy đếm xem có bao nhiêu bộ $k$ chỉ số $(i_1,i_2,\dots ,i_k)$ thỏa mãn đồng thời hai điều kiện:

• $1\le i_1<i_2<\dots <i_k\le n$;
• Đặt $v=a_{i_1}\mid a_{i_2}\mid \dots \mid a_{i_k}$ thì $L\le v\le R$ và $v$ chia hết cho $3$.

Gọi $S$ là đáp số đúng cho bài tập thầy giáo ra, vì $S$ có thể có giá trị rất lớn và để học sinh tập trung vào vấn đề chính của bài toán nên thầy giáo chỉ yêu cầu học sinh đưa ra được phần dư của $S$ khi chia cho ${10}^9+7$.

Yêu cầu: Hãy giúp Nam xác định phần dư của $S$ khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên $n,k,L,R$ $(1\le k\le n\le {10}^6;0\le L\le R\le {10}^6)$;
• Dòng tiếp theo chứa $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ $(a_i\le {10}^6)$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là phần dư của $S$ khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le k\le n\le {10}^6$.
• $0\le L\le R\le {10}^6$.
• $0\le a_i\le {10}^6$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n\le 20$ và $a_i\le 200$ $(1\le i\le n)$.
• Subtask 2 ($20\%$ số điểm): $n\le 200$ và $a_i\le 200$ $(1\le i\le n)$.
• Subtask 3 ($20\%$ số điểm): $L=R$ và mọi $a_i$ $(1\le i\le n)$ là lũy thừa của $2$.
• Subtask 4 ($20\%$ số điểm): $L=R$.
• Subtask 5 ($20\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ