题目内容

小灵正在为一首新曲编排小节。一段旋律由 $m$ 个音符组成，按时间顺序它们的音高依次为 $f_1, f_2, \dots, f_m$，满足 $f_1 \le f_2 \le \dots \le f_m$。

她打算将这段旋律划分成若干连续的小节，每个小节恰好包含 $1$ 个或 $2$ 个音符。当一个节中包含 $2$ 个音符时，它们必须是旋律中相邻的两个音符，即 $(f_{i-1}, f_i)$，并且它们的音高差不能超过一个给定的阈值 $D$，即 $f_i - f_{i-1} \le D$。求合法划分方案的总数。由于答案可能很大，请输出其对 $10^9+7$ 取模的结果。

测试数据组数 $q$ 不超过 10^5。对于每组数据，音符个数 $m$ 不超过 2 × 10^5，且所有数据的 $m$ 之和不超过 2 × 10^5。阈值 $D$ 为 0 到 10^9 之间的整数。每个音高 $f_i$ 满足 $|f_i| \le 10^{18}$，且输入保证 $f_1 \le f_2 \le \dots \le f_m$。

输入描述

第一行包含一个整数 $q$，表示测试数据的组数。接下来每部分描述一组测试数据，每组数据包含两行： 第一行包含两个整数 $m$ 和 $D$，以一个空格分隔； 第二行包含 $m$ 个整数 $f_1, f_2, \dots, f_m$，以空格分隔。

输出描述

对于每组测试数据，输出一行一个整数，表示该组数据对应的合法划分方案数对 $10^9+7$ 取模的结果。

样例1

输入

1
1 0
5

输出

1

说明

只有 1 个音符，$f_1 = 5$。

无论阈值 $D$ 是多少，单音符只能单独成一个小节，因此合法划分方案只有 1 种。

样例2

输入

2
2 2
1 3
2 2
1 4

输出

2
1

说明

第一组数据：$m=2, D=2$，音符为 1 3。$f_2 - f_1 = 3 - 1 = 2 \le D$，两个音符既可以各自单独成节，也可以组成一个二人小节。 两种方案分别是 $(1)(3)$ 和 $(1,3)$，总数为 2。

第二组数据：$m=2, D=2$，音符为 1 4。$f_2 - f_1 = 4 - 1 = 3 > D$，此时二人小节不合法，只能分成两个单独小节 $(1)(4)$。 因此方案数为 1。

样例3

输入

1
5 3
1 3 4 5 9

输出

5

说明

设 $dp[i]$ 表示前 $i$ 个音符的合法方案数。

初始 $dp[0] = 1$，$dp[1] = 1$。

• 第 2 个音符（$f_2=3$）：$3 - 1 = 2 \le 3$，可与前一音符组成二人组，$dp[2] = dp[1] + dp[0] = 1 + 1 = 2$。
• 第 3 个音符（$f_3=4$）：$4 - 3 = 1 \le 3$，$dp[3] = dp[2] + dp[1] = 2 + 1 = 3$。
• 第 4 个音符（$f_4=5$）：$5 - 4 = 1 \le 3$，$dp[4] = dp[3] + dp[2] = 3 + 2 = 5$。
• 第 5 个音符（$f_5=9$）：$9 - 5 = 4 > 3$，不能组成二人组，$dp[5] = dp[4] = 5$。

最终答案为 5。