题目描述

Sashka 正在上体育课。班里共有 N 名学生，编号为 0 到 N - 1。

体育老师希望把所有学生分成若干组一起训练。为了简化管理，每一组必须由编号连续的一段学生组成。一个组也可以只包含 1 名学生。

第 i 名学生的体能值为 A_i。如果某一组中的任意两名学生体能差的绝对值都不超过 K，那么这组训练就是成功的，也就是：

组内最大体能值与最小体能值之差不超过 K

老师并不关心总共分成多少组，只要求：

• 每个学生都恰好属于一个组
• 每个组都是由编号连续的一段学生组成
• 每个组都满足训练成功的条件

请你计算：共有多少种不同的分组方式。答案对 10^9 + 7 取模。

---

实现要求

你需要实现如下函数：

int solve(std::vector<int> A, int K);

其中：

• A：长度为 N 的数组，表示所有学生的体能值
• K：允许的最大体能差

该函数在每个测试中只会被调用一次，你需要返回合法分组方案数对 10^9 + 7 取模后的结果。

---

约束条件

• 1 <= N <= 10^7
• 0 <= A_i, K <= 10^9

---

子任务

子任务	分值	需要通过的前置子任务	N	额外限制
0		-		样例
1	9	0	<= 20	无
2	8	0-1	<= 500
3	9	0-2	<= 10^4
4	6	-	<= 10^5	A_i <= 1000，K = 0
5		0, 4	<= 10^7	无
6	18	0-5	<= 10^5
7	19	0-6	<= 10^6
8	23	0-7	<= 10^7	A_i, K <= 1000

只有当某个子任务及其要求的前置子任务全部通过时，才能获得该子任务的分数。

---

样例 1

输入

3 5
1 4 7

输出

3

---

样例 2

输入

3 6
1 4 7

输出

4

---

样例 3

输入

7 4
8 7 5 6 2 3 7

输出

42

---

本地评测器

输入格式

• 第 1 行：两个整数 N, K
• 第 2 行：A_0 A_1 ... A_{N-1}

输出格式

• 第 1 行：solve 的返回值

---