SOLVE

LATER

Number game

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

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++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"60e5ba7": "/pagelets/problem-author-tester/algorithm/number-game-10/", "60e5b62": "/pagelets/show-submission/algorithm/number-game-10/", "60e5bc4": "/pagelets/problems-hint/algorithm/number-game-10/", "60e5be2": "/pagelets/recommended-problems/algorithm/number-game-10/", "60e5b88": "/pagelets/suggested-problems/algorithm/number-game-10/"}

{}

realtime.hackerearth.com

80

30ff45197d86c2a9afb0162f573fe5466386f145

58a29e5cae2309f04b28

/realtime/pusher/auth/