Problem Description

In a certain house, there are three people: square1001, E869120, and usagi. These three often get into arguments over the differences in the prices of their lunches.

Therefore, square1001 proposed the following:

"I want the difference in the total prices between square1001 and E869120, and also between square1001 and usagi, to be both within D."

→ Both agreed.

There are $ N $ food items, and their prices are $ A_i $. Additionally, up to $ E $ food items can be left over.

How many ways are there to divide the food items to satisfy the conditions?

Input Format

The input is given from the standard input in the following format:

$ N $ $ D $ $ E $ $ A_1 $ $ A_2 $ : $ A_N $

• The first line contains integers $ N $, $ D $, and $ E $ separated by spaces.
• The next $ N $ lines contain the integers $ A_i $.

Output Format

Output the number of ways to divide the food items in one line.

Sample Input and Output

Sample Input #1

3 2 1
2
4
6

Sample Output #1

4

Sample Input #2

4 1 1
1
2
3
4

Sample Output #2

10

Notes/Hints

Constraints

• $2 \leq N \leq 20$
• $0 \leq D \leq 1,000,000,000$
• $0 \leq E \leq 2$
• $1 \leq A_i \leq 1,000,000,000$

Partial Points

This problem has partial points.

• If you correctly solve all cases where $2 \leq N \leq 10$, you will be awarded 20 points.
• If you correctly solve the dataset where $11 \leq N \leq 20$ and the number of ways to divide the food items that satisfy the conditions is $ 1000 $ or less, you will be awarded 50 points.
• If you correctly solve the remaining dataset, you will be awarded 30 points.

Sample Explanation 1

If we denote square1001 as A, E869120 as B, and usagi as C, the items can be divided as follows:

Sample Explanation 2

Problem statement author: E869120

见题面 Input 部分

见题面 Output 部分