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 ≤ N ≤ 40), L, R (1 ≤ L ≤ R ≤ 10^18).
• Dòng thứ hai chứa N số nguyên dương A_i (1 ≤ A_i ≤ 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