#2743. 「JOI Open 2016」摩天大楼

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 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)

样例

样例输入 1

4 10
3 6 2 9

样例输出 1

6

样例说明 1

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

样例输入 2

8 35
3 7 1 5 10 2 11 6

样例输出 2

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 分) \ \ 没有额外限制。