【普及】极差不超过k的分割数

给你一个整数数组 a 和一个整数 $k$。你的任务是将 a 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 $k$。

返回在此条件下将 a 分割的总方法数。

由于答案可能非常大，返回结果需要对 $10^9 + 7$ 取余数。

输入格式

第一行包含 $2$ 个整数 $n, k(2 \le n \le 10^5, 0 \le k \le 10^9)$

第二行包含 $n$ 个整数，表示数组 $a(1 \le a_i \le 10^9)$

输出格式

输出 $1$ 行包含 $1$ 个数，表示答案

5 4
9 4 1 3 7

6

3 0
3 3 4

2

提示

【样例 1 解释】

• 共有 $6$ 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 $k = 4$:
• $[[9], [4], [1], [3], [7]]$
• $[[9], [4], [1], [3, 7]]$
• $[[9], [4], [1, 3], [7]]$
• $[[9], [4, 1], [3], [7]]$
• $[[9], [4, 1], [3, 7]]$
• $[[9], [4, 1, 3], [7]]$

【样例 2 解释】

• 共有 $2$ 种有效的分割方式，满足给定条件：
• $[[3], [3], [4]]$
• $[[3, 3], [4]]$

【数据范围】

• $2 \le n \le 10^5$
• $0 \le k \le 10^9$
• $1 \le a_i \le 10^9$

来源

• 参考答案