All Tracks Math Combinatorics Basics of Combinatorics Problem

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...
Your Rating:

Contributor

This Problem was Asked in

Goodbox

Challenge Name

Goodbox Internship Hack

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications