题目内容

给定 $n$ 个人的权值序列 $a_1,a_2,\dots,a_n$，保证 $a$ 已按非降序排列。

需要将所有人分成若干组，每组人数只能为 $1$ 或 $2$。规则如下：

1. 单人一组不受限制。
2. 两人一组时，必须选择下标相邻的两个人 $(i-1,i)$，并满足 $|a_i - a_{i-1}| \le K$。

请你计算共有多少种合法的分组方案，答案对 $10^9 + 7$ 取模。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^5)$ 表示数据组数，每组测试数据描述如下：

第一行输入两个整数 $n, K\ (1 \le n \le 2 \times 10^5,\ 0 \le K \le 10^9)$。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (|a_i| \le 10^{18})$，并保证 $a_1 \le a_2 \le \dots \le a_n$。

保证所有测试中 $n$ 的总和不超过 $2 \times 10^5$。

输出描述

输出 $T$ 行，每行输出一个整数，表示合法分组方案数对 $10^9 + 7$ 取模后的结果。

样例1

输入

3
4 1
1 2 4 10
4 0
1 2 3 4
5 2
1 1 2 4 7

输出

2
1
5

说明

第一组：只有相邻的 $(1,2)$ 满足差值不超过 $K$，因此方案为：全单人；或 $(1,2)$ 配对其余单人，共 $2$ 种。

第二组：相邻差均大于 $0$，无法配对，只能全单人，答案为 $1$。