小组项目

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

班级中有 $n$ 名学生。第 $i$ 名学生完成独立部分需要 $a_i$ 分钟。你需要把所有学生划分成若干个非空小组，单人组也是允许的。

一个小组的不平衡度等于组内最大的 $a_i$ 减去最小的 $a_i$；单人组的不平衡度为 $0$。一种划分的总不平衡度是所有小组不平衡度之和。

求总不平衡度不超过 $k$ 的不同划分数。若存在一对学生在一种划分中同组、另一种划分中不同组，则两种划分不同。答案对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出满足条件的划分数对 $10^9+7$ 取模后的结果。

样例输入 1

3 2
2 4 5

样例输出 1

3

样例输入 2

4 3
7 8 9 10

样例输出 2

13

样例输入 3

4 0
5 10 20 21

样例输出 3

1

数据范围

对于所有数据，$1\le n\le200$，$0\le k\le1000$，$1\le a_i\le500$。

提示

第一个样例中的三种方案分别为：学生 $1,2$ 同组；学生 $2,3$ 同组；所有学生均单独成组。