Doraemon's Diet Dilemma

Doraemon, our beloved robotic cat, has n portions of food with energy values \(w[1], w[2], \ldots, w[n]\). At lunchtime, he can choose some of these portions to eat. By eating a subset of foods, he obtains a total energy equal to the sum of the energies of the chosen portions.

However, to maintain his perfect figure, Doraemon wants his total energy intake to lie within a specific target range \([l, r]\). There may be many ways to choose a subset of food that leads to a total energy in this interval. Your task is to count the number of ways Doraemon can choose his food so that the total energy is between \(l\) and \(r\) (inclusive).

Note: The empty subset (choosing no food) is also considered.

The problem can be formally described by the equation:

[ \text{Find the number of subsets } S \subseteq {1,2,\ldots,n} \text{ such that } l \leq \sum_{i \in S} w[i] \leq r. ]

inputFormat

The first line contains three integers: n (the number of food portions), l and r, representing the target range \([l, r]\).

The second line contains n integers \(w[1], w[2], \ldots, w[n]\) where \(w[i]\) represents the energy of the i-th food portion.

outputFormat

Output a single integer: the number of ways to choose a subset of foods such that the total energy lies in the range \([l, r]\).

sample

3 3 5
1 2 3

4