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 ≤ K ≤ N ≤ 40
• 1 ≤ ai ≤ 1016
• 1 ≤ L ≤ R ≤ 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.

Examples

Input

2 2 1 9 5 1

Output

1

Input

5 2 7 19 3 5 4 2 2

Output

5

inputFormat

input values are given in integers

Input

The input is given in the following format.

N K L R a1 a2 ... aN

outputFormat

Output

Print the number of combinations in a line.

Examples

Input

2 2 1 9 5 1

Output

1

Input

5 2 7 19 3 5 4 2 2

Output

5

样例

5 2 7 19
3 5 4 2 2

5