cubes

Time limit: 0.7s
Memory limit: 256MB
Input:
Output:

Among her toys, Octavia has N cubes of identical size. The cubes might differ in weight, but it is also possible for two cubes to have the same weight. Octavia enjoys setting her cubes in a long sequence and after many hours playing with them, she started wondering about the number of different sequences of cubes that can be obtained.

The sequence of cubes is represented by N integers, where each one corresponds to the weight of the corresponding cube in the initial sequence. Octavia can pick two adjacent cubes and swap them if and only if their total weight is not larger than the integer K. Octavia may repeat the operation of swapping any two adjacent cubes with total weight not larger than K infinitely many times. Two sequences are considered different if their corresponding sequences of cube weights are different.

Let us take as an example the following case with 4 cubes with weights [1, 2, 1, 3] and K = 3. There are 3 possible cube sequences that can be obtained. The first of those is the initial sequence.

To obtain the second sequence, we can swap cubes at positions 2 and 3 from the initial sequence to obtain the sequence: [1, 1, 2, 3]. Note that we cannot swap cubes 1 and 3 in the initial sequence, because they are not adjacent. We also cannot swap cubes 3 and 4, because their total weight is 4, which is larger than K = 3. We can obtain the last sequence by swapping the first two cubes in the initial sequence and obtain [2, 1, 1, 3]. Note that if we start with the initial sequence and K = 1, there is just one possible sequence; when K = 2, there is just one sequence as well; if K = 4, there are 6 sequences; when K = 5, there are 12 sequences.

Task

Write a program which solves the task Sashka is given.

Input

There are 2 integers on the first line: N - the number of cubes and K - the maximum total weight of two adjacent cubes that can be swapped. There will be N positive integers wiw_i, on the second line of the input, corresponding to the weights in the initial sequence.

Output

Print the number of possible permutations modulo 1 000 000 007 to the standard output.

Constraints

  • 1 ≤ N ≤ 300 000
  • 0 ≤ K ≤ 2 000 000 000
  • 0wi1 000 000 0000 ≤ w_i ≤ 1 \ 000 \ 000 \ 000

Subtask 1 (7 points)

  • N ≤ 7
  • All weights are different

Subtask 2 (23 points)

  • N ≤ 100
  • All weights are different

Subtask 3 (15 points)

  • N ≤ 1 000
  • All weights are different

Subtask 4 (15 points)

  • N ≤ 1 000

Subtask 3 (21 points)

  • N ≤ 100 000
  • All weights are different

Subtask 4 (19 points)

  • N ≤ 300 000

Examples

stdin

4 5
1 2 1 3

stdout

12

stdin

5 4
4 3 1 5 2

stdout

2

Explanation

Example #1: In problem statement.

Example #2: We can only swap the cubes with weight 1 and 5, so the answer is 2, and the two possible sequences are [4, 3, 1, 5, 2] and [4, 1, 3, 5, 2].

Problem info

ID: 311

Editor: liviu

Source: IATI Shumen 2022 Senior: Day 1, Problem 1

IATI Shumen 2022 Senior: Day 1

Log in or sign up to be able to send submissions!