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 , 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 0000 ≤ K ≤ 2 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].