#681. 奶牛排队

奶牛排队

大样例下载

题目描述

Farmer John 有 NN 头奶牛,身高分别为 H1,H2,……,HNH_1, H_2, ……, H_N。奶牛的身高两两不同。

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

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

问:John 有多少种排队方案?输出答案 mod (109+7)(10^9+7)。

输入格式

第一行:包含两个整数 N,MN, M;

第二行:包含 NN 个整数 HiH_i。

输出格式

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

样例输入

3 5
3 1 5

输出

2

样例解释

符合条件的排列有两种:

1 3 5

5 3 1

数据规模与约定

对于所有数据,1≤N≤1001 ≤ N ≤ 100,1≤M≤10001 ≤ M ≤ 1000,1≤Hi≤10001 ≤ H_i ≤ 1000。

  • 有 5% 的数据:N≤8N ≤ 8。
  • 另有 15% 的数据:N≤14N ≤ 14,M≤100M ≤ 100。