Elearning CodePath – CTP Online Judge

OR - OR

2024_DHBB_SOSDP_B007

🟢 Easy

Một trung tâm nghiên cứu lưu trữ thông tin của `n` mẫu vật, được đánh số từ `1` đến `n`. Mẫu vật thứ `i` được mô tả bởi một số nguyên không âm `A_i`.

Để tổng hợp thông tin của một nhóm mẫu vật, trung tâm sử dụng phép toán OR theo bit. Với hai số nguyên không âm `x` và `y`, một bit của `x | y` bằng `1` nếu bit tương ứng của ít nhất một trong hai số bằng `1`.

Với một nhóm gồm các mẫu vật có chỉ số `i_1 < i_2 < ... < i_k`, gọi giá trị tổng hợp của nhóm là `A[i_1] | A[i_2] | ... | A[i_k]`.

Một nhóm được gọi là hợp lệ nếu giá trị tổng hợp nằm trong đoạn `[L,R]` và chia hết cho `3`. Hai cách chọn được coi là khác nhau nếu chúng khác nhau ở ít nhất một chỉ số được chọn.

Hãy xác định có bao nhiêu cách chọn đúng `k` mẫu vật để tạo thành một nhóm hợp lệ. Do số cách có thể rất lớn, đưa ra kết quả modulo `1000000007`.

### Input
- Dòng đầu chứa `n k L R`.
- Dòng thứ hai chứa `n` số nguyên không âm `A_1, A_2, ..., A_n`.

### Output
In một số nguyên duy nhất - số cách chọn nhóm hợp lệ, lấy modulo `1000000007`.

### Constraints chuẩn hóa
- `1 <= k <= n <= 200000`.
- `0 <= A_i < 2^20`.
- `0 <= L <= R < 2^20`.

### Subtasks
- S1 - 20 điểm: `n <= 24`.
- S2 - 20 điểm: `k = 1`.
- S3 - 20 điểm: mọi `A_i < 2^12`.
- S4 - 20 điểm: `n <= 5000`.
- S5 - 20 điểm: không có ràng buộc bổ sung.

### Ví dụ
```text
Input
5 3 3 15
1 2 4 8 3

Output
2
```

✅ Đã AC: 6 / 8 submissions