## SUBSUMS - Subset Sums

Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 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.

### Input

The first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN, in order.

### Output

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.

### Example

```Input:
3 -1 2
1
-2
3

Output:
5
```

The following 5 subsets have a sum between -1 and 2:

• 0 = 0 (the empty subset)
• 1 = 1
• 1 + (-2) = -1
• -2 + 3 = 1
• 1 + (-2) + 3 = 2

 < Previous 1 2 3 4 5 6 Next > pankaj: 2009-08-30 11:22:46 what should do if there is an element in set value "0". 1.if empty set and {0} are same? 2.if s={1,-2,0} then {1,0}and {1}are different set? 3.if two or more elements can be same of every element will different? Last edit: 2009-08-30 11:24:13