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...