SP3749 SUBSUMS - Subset Sums

Given a sequence of N (1 ≤ N ≤ 34) numbers S $ _{1} $ , ..., S $ _{N} $ (-20,000,000 ≤ S $ _{i} $ ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum between A and B (-500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.

The first line of standard input contains the three integers N, A, and B. The following N lines contain S $ _{1} $ through S $ _{N} $ , in order.

Print a single integer to standard output representing the number of subsets satisfying the above property. Note that the answer may overflow a 32-bit integer.