Cubes

Octavia has $N$ cubes of identical size among her toys. The cubes may differ in weight, and two cubes may also share the same weight. Octavia likes to set the cubes in a long row. After many hours of play, she started to wonder how many different rows of cubes she can make.

A row of cubes is given as $N$ integers, where each integer is the weight of the corresponding cube in the initial row. Octavia can swap two adjacent cubes only if their total weight is at most $K$. She may repeat this swap on any adjacent pair as many times as she wants. Two rows are different if their sequences of cube weights differ.

For example, take 4 cubes with weights $[1, 2, 1, 3]$ and $K = 3$. There are 3 possible rows. The first is the initial row. To get the second, swap the cubes at positions 2 and 3 to get $[1, 1, 2, 3]$. The cubes at positions 1 and 3 cannot be swapped because they are not adjacent. The cubes at positions 3 and 4 cannot be swapped because their total weight is 4, which is larger than $K = 3$. The last row comes from swapping the first two cubes, giving $[2, 1, 1, 3]$. With the same initial row and $K = 1$, there is only one possible row. With $K = 2$, there is also only one. With $K = 4$, there are 6 rows, and with $K = 5$, there are 12 rows.

Write a program named cubes that finds the number of different rows of cubes Octavia can obtain.

The first line has two integers $N$, the number of cubes, and $K$, the maximum total weight of two adjacent cubes that can be swapped. The second line has $N$ positive integers $w_1, \dots, w_N$, the weights in the initial row.

Print a single line with the number of possible rows, modulo $1\,000\,000\,007$.

$1 \le N \le 300\,000$

$1 \le w_i, K \le 1\,000\,000\,000$

In the second case, only the cubes with weights 1 and 3 can be swapped, so the answer is 2. The two possible rows are $[4, 3, 1, 5, 2]$ and $[4, 1, 3, 5, 2]$.