28477번 - Cubes 서브태스크다국어

문제

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 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 at positions 1ドル$ and 3ドル$ in the initial sequence, because they are not adjacent. We also cannot swap the cubes at positions 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.

Write a program cubes, which helps Octavia find the number of different sequences of cubes.

입력

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 $w_1, \dots , w_N,ドル on the second line of the input, corresponding to the weights in the initial sequence.

출력

A single line with the number of possible sequences that Octavia can obtain, modulo 1ドル,000円,000円,007円$.

제한

• 1ドル ≤ N ≤ 300,000円$
• 1ドル ≤ w_i , K ≤ 1,000円,000円,000円$

서브태스크

힌트

Example No1: In problem statement.

Example No2: We can only swap the cubes with weights 1ドル$ and 3ドル,ドル so the answer is 2ドル,ドル and the two possible sequences are $[4, 3, 1, 5, 2]$ and $[4, 1, 3, 5, 2]$.