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 | 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 ~a_1, a_2, \dotsc, 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, \dotsc, i_k)~ thỏa mãn đồng thời hai điều kiện:

• ~1 \le i_1 < i_2 < \dotsc < i_k \le n~.
• Đặt ~v = a_{i_1} | a_{i_2} | \dotsc | 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 từ đầu vào chuẩn (không phải file OR.INP):

• 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, \cdots, 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.

Kết quả

Ghi ra đầu ra chuẩn (không phải file 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 \le 20~ và ~a_i \le 200 (1 \le i \le n)~;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~n \le 200~ và ~a_i \le 200 (1 \le i \le n)~;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~L = R~ và ~a_i(1 \le i \le n)~ là lũy thừa của 2;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~L = R~ ;
• Có ~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.

Ví dụ

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:

1. ~a_1 | a_2 = 1 | 2 = 3~
2. ~a_2 | a_4 = 2 | 6 = 6~
3. ~a_2 | a_5 = 2 | 4 = 6~
4. ~a_4 | a_5 = 6 | 4 = 6~