Background

Translated from T3 「高層ビル街 / Skyscraper」 of JOI Open 2016.

Problem Description

Arrange $N$ pairwise distinct integers $A_1, A_2, \cdots, A_N$ in some order.

Suppose the arrangement is $f_1, f_2, \cdots, f_N$. It must satisfy: $| f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| \leq L$.

Find the number of arrangements that satisfy the requirement, modulo $10^9+7$.

Input Format

The input consists of two lines.

The first line contains two integers $N, L$.
The second line contains $N$ integers $A_1, A_2, \cdots, A_N$.

Output Format

Output one integer in a single line, representing the number of valid arrangements modulo $10^9+7$.

4 10
3 6 2 9

6

8 35
3 7 1 5 10 2 11 6

31384

Hint

Explanation for Sample 1

The six valid arrangements are:

$$\begin{matrix} 2\ 3\ 6\ 9,& |2 - 3| + |3 - 6| + |6 - 9| &=& 7 \\ 2\ 3\ 9\ 6,& |2 - 3| + |3 - 9| + |9 - 6| &=& 10 \\ 3\ 2\ 6\ 9,& |3 - 2| + |2 - 6| + |6 - 9| &=& 8 \\ 6\ 9\ 3\ 2,& |6 - 9| + |9 - 3| + |3 - 2| &=& 10 \\ 9\ 6\ 2\ 3,& |9 - 6| + |6 - 2| + |2 - 3| &=& 8 \\ 9\ 6\ 3\ 2,& |9 - 6| + |6 - 3| + |3 - 2| &=& 7 \\ \end{matrix}$$

Constraints

This problem uses bundled testdata.

For all testdata, $1\le N\le 100$, $1\le L\le 1000$, $1\le A_i\le 1000$.

• Subtask 1 (5 points): $N\le 8$.
• Subtask 2 (15 points): $N\le 14$, $L\le 100$.
• Subtask 3 (80 points): No additional constraints.

Translated by ChatGPT 5