Number game
Tag(s):

## Data Structures, Easy-Medium, approved, hiring

Problem
Editorial
Analytics

Given an array $A$ consisting of integers of size $N$ and $2$ additional integers $K$ and $X$, you need to find the number of Subsets of this array of size $K$, where Absolute difference between the Maximum and Minimum number of the subset is at most $X$.

As this number that you need to find can be rather large, print it Modulo $10^9+7$

Input Format :

The first line contains $3$ space separated integers denoting $N$, $K$ and $X$. The next line contains $N$ space separated integers, where the $i^{th}$ integer denotes $A[i]$.

Output Format:

Print the required answer on a single line. As the answer can be rather large, print it Modulo $10^9+7$.

Constraints:

$1 \le N \le 5 \times 10^5$

$1 \le K \le N$

$1 \le A[i],X \le 10^9$

Note :

Note that it may be possible that the maximum and minimum element of a subset may be equal to each other. $2$ subsets are considered different if they differ in atleast one index picked from the array $A$.

SAMPLE INPUT
5 3 5
1 2 3 4 5
SAMPLE OUTPUT
10
Explanation

One of the ways to pick a subset is : $[5,3,1]$. For this array, each subset of size $3$ is a valid pick.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...