Tập con

Bạn được cho một mảng gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) và hai số nguyên \(A\) và \(B\).

Hãy đếm xem có bao nhiêu tập con khác nhau của mảng \(a\) sao cho tổng các phần tử trong tập con nằm trong đoạn \([A, B]\).

Chú ý: Hai tập con được xem là khác nhau nếu tập chỉ số các phần tử khác nhau. Một tập con có thể có \(0\) phần tử.

Input

Dòng đầu tiên chứa ba số nguyên \(n\), \(A\), \(B\) \((1 \le n \le 40, 0 \le A \le B \le 10^9)\).

Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 10^9)\).

Output

In ra một số nguyên duy nhất — số lượng tập con có tổng thuộc đoạn \([A, B]\).

Sample Input 1

4 3 6
1 2 3 4

Sample Output 1

8