Shopping

1.8

9 votes
Dynamic Programming, Algorithms, Math, Introduction to Dynamic Programming 1
Problem

There are two brothers name Hazel (Bob) and Laurel (James). Their mom told them to buy n products from the store. There is one condition according to which they can shop:

Bob can bring the items that have the price difference greater than or equal to X with each other and James can bring the items that have the price difference greater than or equal to Y with each other. 

You are required to determine the number of ways in which both of them can bring the items home.

Note: As the number of ways can be greater, print the answer modulo 1e9+7.

Input format

  • The first line contains three integers n, X, and Y denoting the number of items, the price difference for Bob, and the price difference for James respectively.
  • The second line contains n integers where Ai denotes the prices of the products.

Output format

Print the number of ways modulo 1e9+7.

Constraints

1N1e51X, Y1e180Ai1e18

Sample Input
8 2 9
3
4
5
13
15
22
26
32
Sample Output
13
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

The answer for the input is 13.

Editor Image

?