CF626F.Group Projects

There are n students in a class working on group projects. The students will divide into groups (some students may be in groups alone), work on their independent pieces, and then discuss the results together. It takes the i-th student a__i minutes to finish his/her independent piece.

If students work at different paces, it can be frustrating for the faster students and stressful for the slower ones. In particular, the imbalance of a group is defined as the maximum a__i in the group minus the minimum a__i in the group. Note that a group containing a single student has an imbalance of 0. How many ways are there for the students to divide into groups so that the total imbalance of all groups is at most k?

Two divisions are considered distinct if there exists a pair of students who work in the same group in one division but different groups in the other.

班上有 $n$ 名学生正在合作完成小组项目。学生们将分成若干组（部分学生可能单独成组），各自完成独立任务，然后一起讨论结果。第 $i$ 名学生完成其独立任务需要 $a_i$ 分钟。

若学生工作速度不同，对较快的学生而言会令人沮丧，对较慢的学生而言则会造成压力。特别地，一个小组的不平衡度定义为该组中所有 $a_i$ 的最大值减去最小值。注意：仅含一名学生的小组，其不平衡度为 $0$。问：有多少种分组方式，使得所有小组的不平衡度之和不超过 $k$？

如果存在两名学生，在一种分组方案中同组、而在另一种分组方案中不同组，则认为这两种分组方案是不同的。

The first line contains two space-separated integers n and k (1 ≤ n ≤ 200, 0 ≤ k ≤ 1000) — the number of students and the maximum total imbalance allowed, respectively.

The second line contains n space-separated integers a__i (1 ≤ a__i ≤ 500) — the time it takes the i-th student to complete his/her independent piece of work.

第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 ≤ n ≤ 200$，$0 ≤ k ≤ 1000$），分别表示学生人数和允许的最大总失衡值。

第二行包含 $n$ 个以空格分隔的整数 $a_i$（$1 ≤ a_i ≤ 500$），表示第 $i$ 个学生完成其独立作业所需的时间。

Print a single integer, the number of ways the students can form groups. As the answer may be large, print its value modulo 109 + 7.

输出一个整数，表示学生组成小组的方式数目。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

In the first sample, we have three options:

• The first and second students form a group, and the third student forms a group. Total imbalance is 2 + 0 = 2.
• The first student forms a group, and the second and third students form a group. Total imbalance is 0 + 1 = 1.
• All three students form their own groups. Total imbalance is 0.

In the third sample, the total imbalance must be 0, so each student must work individually.

在第一个样例中，我们有三种分组方式：

• 第一和第二名学生组成一组，第三名学生单独成组。总不平衡度为 $2 + 0 = 2$。
• 第一名学生单独成组，第二和第三名学生组成一组。总不平衡度为 $0 + 1 = 1$。
• 三名学生各自单独成组。总不平衡度为 $0$。

在第三个样例中，总不平衡度必须为 $0$，因此每名学生都必须单独工作。