Counting - Coin Combination Problem II

Time Limit : 3 sec, Memory Limit : 262144 KB
Japanese version is here

Coin Combination Problem II

You have N coins each of which has a value ai. Find the number of combinations that result when you choose K different coins in such a way that the total value of the coins is greater than or equal to L and less than or equal to R.

Constraints

  • 1 ≤ KN ≤ 40
  • 1 ≤ ai ≤ 1016
  • 1 ≤ LR ≤ 1016
  • All input values are given in integers

Input

The input is given in the following format.

N K L R
a1 a2 ... aN

Output

Print the number of combinations in a line.

Sample Input 1

2 2 1 9
5 1

Sample Output 1

1

Sample Input 2

5 2 7 19
3 5 4 2 2

Sample Output 2

5