国际信息学奥林匹克竞赛（IOI）即将在日本筑波市举行。为了迎接 IOI，我们计划在筑波市的主干道上建造摩天大楼。为了打造一个新的观光景点，这些建筑必须满足以下条件。

我们计划在主干道上沿直线建造 $N$ 座建筑。它们的高度分别为 $A_1, A_2, A_3, \dots, A_N$，且各不相同。由于 $N$ 座建筑的排列顺序尚未确定，我们可以根据需要对它们的高度进行排列。由于装饰材料的限制，相邻两座建筑高度差的绝对值之和必须小于或等于 $L$。换句话说，如果主干道一侧的建筑高度依次为 $f_1, f_2, f_3, \dots, f_N$，则必须满足 $|f_1 - f_2| + |f_2 - f_3| + \dots + |f_{N-1} - f_N| \le L$。其中 $|x|$ 表示 $x$ 的绝对值。

请问有多少种建筑的排列方式满足上述条件？

题目描述

给定建筑的数量 $N$、它们的高度以及相邻两座建筑高度差的绝对值之和的上限 $L$，编写一个程序，计算满足条件的建筑排列方式的数量。由于该数字可能非常大，请输出其除以 $1\,000\,000\,007$ 的余数。

输入格式

从标准输入读取以下数据。

• 第一行包含两个空格分隔的整数 $N, L$。这表示建筑的数量为 $N$，相邻两座建筑高度差的绝对值之和的上限为 $L$。
• 第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, A_3, \dots, A_N$。这表示第 $i$ 座建筑（$1 \le i \le N$）的高度为 $A_i$。

输出格式

输出一行，包含一个整数，即满足条件的建筑排列方式数量除以 $1\,000\,000\,007$ 的余数。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 100$
• $1 \le L \le 1\,000$
• $1 \le A_i \le 1\,000$ ($1 \le i \le N$)
• $A_i \neq A_j$ ($1 \le i < j \le N$)

子任务

子任务 1 [5 分]

• $N \le 8$

子任务 2 [15 分]

满足以下条件：

• $N \le 14$
• $L \le 100$

子任务 3 [80 分]

• 无附加限制。

样例

样例输入 1

4 10
3 6 2 9

样例输出 1

6

说明

总共有 24 种排列方式。其中有 6 种排列方式满足相邻建筑高度差的绝对值之和小于或等于 10：

• 若 $f_1 = 2, f_2 = 3, f_3 = 6, f_4 = 9$，则 $|2 - 3| + |3 - 6| + |6 - 9| = 7$。
• 若 $f_1 = 2, f_2 = 3, f_3 = 9, f_4 = 6$，则 $|2 - 3| + |3 - 9| + |9 - 6| = 10$。
• 若 $f_1 = 3, f_2 = 2, f_3 = 6, f_4 = 9$，则 $|3 - 2| + |2 - 6| + |6 - 9| = 8$。
• 若 $f_1 = 6, f_2 = 9, f_3 = 3, f_4 = 2$，则 $|6 - 9| + |9 - 3| + |3 - 2| = 10$。
• 若 $f_1 = 9, f_2 = 6, f_3 = 2, f_4 = 3$，则 $|9 - 6| + |6 - 2| + |2 - 3| = 8$。
• 若 $f_1 = 9, f_2 = 6, f_3 = 3, f_4 = 2$，则 $|9 - 6| + |6 - 3| + |3 - 2| = 7$。

样例输入 2

8 35
3 7 1 5 10 2 11 6

样例输出 2

31384