SP31902 PARAG - Paragliding Trip

你了解滑翔伞吗？这是一项休闲运动，运动员从高处跃下，携带伞翼在空中滑翔。尽管气流或许能提供一些支撑，但最终重力还是会把人拉向地面。 在斯洛伐克斯坦，滑翔伞运动有一群热爱者，他们组成了“斯洛伐克斯坦滑翔伞俱乐部”（Klub Slovakistanských Paraglidistov，即 KSP）。正如所有真正的兴趣小组，KSP 组织了俱乐部活动——集体前往最理想的滑翔伞胜地，让会员们在壮丽的山脉间尽情滑翔。而每一次的旅行都要比上一次更精彩，这是至关重要的。今年尤其如此，因为斯洛伐克斯坦滑翔伞超明星 Syseľ 答应一起参加。Syseľ 对滑翔伞运动的钟爱及其奉献精神，让他在国际滑翔伞界享有很高的知名度。 在 Syseľ 的畅销自传里，KSP 的成员了解到他最喜欢长时间飞行，即他所飞跃山峰的起跳和降落点之间的高度差必须大于**m**。在一次专访中，他还提到他最不喜欢的是每次飞行后都要费力爬上山；因此，他习惯于从高山起跳、降落至较低的山，然后再从这较低的山继续起跳，如此反复。如果他连续完成了 **s-1** 次的跳跃，他就很满意。而从成员们截获的电话中，他们得知 Syseľ 喜欢餐后往东飞，因为往西飞时太阳会刺眼。 为了不辜负 Syseľ 的期待，KSP 正在寻找一处合适的山脉，帮助他们！ ### 任务 每条山脉由 **n** 座山峰组成，可以用一个数组来表示，数组中的数字代表从西到东的山的高度。 一次“旅程”是一个由几座可能不相邻的山峰组成的序列，它要满足 Syseľ 的要求：序列中恰有 **s** 座山，而且每相邻两座山之间的高度差都必须大于 **m**。也就是说，若一山的高度为 **x**，而序列中紧接着的下一山的高度为 **y**，那么 **x-y>m**。 对于给定的由 **n** 座山组成的山脉，以及给定的 **m** 和 **s** 值，找出满足 Syseľ 条件的旅程的数量。

第一行输入一个整数表示测试数据的数量。 每组测试数据的第一行包含三个整数 **n**, **m** 和 **s**，分别是山脉中的山峰数量、所需的高度差以及满足 Syseľ 的旅程需要的山峰数量。 第二行包含 **n** 个整数，表示从西向东的每座山的高度。这些高度都是不超过 $10^{18}$ 的正整数。 所有测试数据中，山峰数量的总和不超过 **400,000**。

对于每组测试数据，输出格式为 "Case **x**: **y**"，其中 **x** 是测试数据的编号，从 1 开始，**y** 是满足 Syseľ 条件的旅程数量，结果需要对 $10^9 + 7$ 取模。若两个旅程有不同的山峰，则视为不同的旅程。

- $1 \le n \le 400,000$ - $0 \le m \le 10^{18}$ - $2 \le s \le n$ - $\sum n \le 400,000$ **本翻译由 AI 自动生成**