题目描述

译自 JOI Open 2016 T3 「高層ビル街 / Skyscraper」

将互不相同的 $N$ 个整数 $A_1, A_2, \dots, A_N$ 按照一定顺序排列。
假设排列为 $f_1, f_2, \dots, f_N$，要求：$ | f_1 − f_2| + | f_2 − f_3| + \dots + | f_{N−1} − f_N| ≤ L$。
求满足题意的排列的方案数 $\bmod (10^9+7)$。

输入格式

第一行有两个整数 $N, L$。
第二行有 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

一行，一个整数，表示方案数 $\bmod (10^9+7)$。

4 10
3 6 2 9

6

$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$。

8 35
3 7 1 5 10 2 11 6

31384

数据范围与提示

对于所有数据，$1\le N\le 100,$ $1\le L\le 1000,$ $1\le A_i\le 1000$。

子任务 1（5 分） $\ \ N\le 8$。
子任务 2（15 分） $\ \ N\le 14,$ $L\le 100$。
子任务 3（80 分） $\ \$没有额外限制。