← 返回题目列表

Codeforces · 626/F

F. 小组项目

中文机器翻译题面 查看原题

班级中有 n 名学生正在进行小组项目。学生将分成小组(有些学生可能单独分组),完成他们的独立作品,然后一起讨论结果。第 i 个学生 ai 需要几分钟才能完成他/她的独立作品。

如果学生以不同的速度学习,速度较快的学生可能会感到沮丧,而速度较慢的学生可能会感到压力。特别地,组的不平衡性被定义为组中的最大ai减去组中的最小ai。请注意,包含单个学生的组的不平衡度为 0。有多少种方法可以将学生分组,使得所有组的总不平衡度最多为 k?

如果存在一对学生在一个部门的同一小组工作但在另一个部门的不同小组,则两个部门被视为不同。

输入

第一行包含两个以空格分隔的整数 n 和 k (1 ≤ n ≤ 200, 0 ≤ k ≤ 1000) – 分别是学生人数和允许的最大总失衡。

第二行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 500) - 第 i 个学生完成他/她的独立作业所需的时间。

输出

打印一个整数,即学生可以组成小组的方式数。由于答案可能很大,因此打印其模 109 + 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

注意

在第一个示例中,我们有三个选项:

- 第一名和第二名学生组成一组,第三名学生组成一组。总不平衡度为2 + 0 = 2。
- 第一个学生组成一组,第二个和第三个学生组成一组。总不平衡度为0 + 1 = 1。
- 所有三个学生组成自己的小组。总不平衡度为0。

在第三个样本中,总不平衡必须为 0,因此每个学生必须单独工作。