Nội dung chính trong tiết 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 hai số nguyên không âm x và y là một số nguyên không âm z trong đó bit thứ í trong biểu diễn nhị phân của z sẽ là 0 khi và chi khi bịt thứ í 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 sẽ 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 | 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 |y = y | x và x | (y | z) = (x | y) | 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 a1, a2, ..., an và ba số nguyên k, L, R. Hãy đếm xem có bao nhiêu bộ k chỉ số (i1, i2, ... ik) thỏa mãn đồng thời hai điều kiện:

• 1 <= i1 < i2 < ... < ik <= n

• Đặt v = ai1 | ai2 | ... | aik thì L <= v <= R và v chia hết cho 3.

Gọi S là đáp số đúng của 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 từ file văn bản OR.INP:

Dòng đầu tiên chứa bốn số nguyên n, k, L, R (1 ≤ k <= n <= 10^6, 0 ≤ L <= R ≤ 10^6):

Dòng tiếp theo chứa n số nguyên không âm a1, a2, ... (ai <= 10^6);

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

Kết quả: Ghi ra file văn bản OR.OUT 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:

• Có 20% số test ứng với 20% số điểm của bài thóa mãn: n ≤ 20 và ai ≤ 200 (1 <= i <= n);

• 20% số test khác ứng với 20% số điểm của bài thoa mãn: n ≤ 200 và a ≤ 200 (1 ≤ i ≤ n):

• 20% số test khác ứng với 20% số điểm của bải thoa mãn: L = R và ai, (1 <= i <= n) là lãy thừa của 2;

• 20% số test khác ứng với 20% số điểm của bài thoa mãn: L = R;

• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Input:

5 2 1 7
1 2 5 6 4

Output:

4

Giải thích: Có tất cả 4 cách chọn 2 số trong 5 số thỏa mãn yêu cầu:

a1|a2 = 1|2 = 3

a2|a4 = 2|6 = 6

a2|a5 = 2|4 = 6

a4|a5 = 6|4 = 6