大样例下载

题目描述

Farmer John 有 $N$ 头奶牛，身高分别为 $H_1, H_2, ……, H_N$。奶牛的身高两两不同。

现在 John 要将这些奶牛排成一队。定义队伍的参差度为 “所有 相邻两头奶牛身高差 之和”。形式化地，设排队后的奶牛身高序列为 $X_1, X_2, ……, X_N$，则队伍的参差度 $S = \sum_{i=1}^{N-1} |X_i - X_{i+1}|$。

显然，队伍的参差度太大，会使得队伍看上去很不整齐，所以 John 希望排队后，队伍的参差度不超过一个给定的值 $M$。

问：John 有多少种排队方案？输出答案 mod $(10^9+7)$。

输入格式

第一行：包含两个整数 $N, M$；

第二行：包含 $N$ 个整数 $H_i$。

输出格式

一个整数，表示 答案 mod $(10^9+7)$。

样例输入

3 5
3 1 5

输出

2

样例解释

符合条件的排列有两种：

1 3 5

5 3 1

数据规模与约定

对于所有数据，$1 ≤ N ≤ 100$，$1 ≤ M ≤ 1000$，$1 ≤ H_i ≤ 1000$。

• 有 5% 的数据：$N ≤ 8$。
• 另有 15% 的数据：$N ≤ 14$，$M ≤ 100$。