Cho mảng A gồm N số nguyên dương. Hãy đếm số lượng tập con có tổng nằm trong đoạn [L, R] (bao gồm cả L và R).

Sử dụng Meet in the Middle: chia mảng làm 2 nửa, sinh tất cả tổng tập con của mỗi nửa. Sắp xếp nửa thứ hai, với mỗi tổng s ở nửa đầu, dùng binary search đếm số tổng ở nửa thứ hai thuộc [L - s, R - s].

Đầu vào

• Dòng đầu tiên chứa ba số nguyên N (\(1 \le N \le 40\)), L, R (\(1 \le L \le R \le 10^18\)).
• Dòng thứ hai chứa N số nguyên dương \(A_i\) (\(1 \le A_i \le 10^15\)).

Đầu ra

Số lượng tập con có tổng thuộc [L, R].

Ví dụ

Input:
6 10 20
2 3 5 8 13 21

Output:
12

Ràng buộc & Subtasks