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++,
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

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"d4a12e4": "/pagelets/suggested-problems/algorithm/number-game-10/", "0284c43": "/pagelets/show-submission/algorithm/number-game-10/", "5ba6a66": "/pagelets/recommended-problems/algorithm/number-game-10/", "f4c1962": "/pagelets/problems-hint/algorithm/number-game-10/", "897e5c1": "/pagelets/problem-author-tester/algorithm/number-game-10/"}

realtime.hackerearth.com

80

30ff45197d86c2a9afb0162f573fe5466386f145

58a29e5cae2309f04b28

/realtime/pusher/auth/