You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

志愿者分组

题目描述

开放日共有 $n$ 名志愿者排成一列，第 $i$ 名志愿者的能力值为 $a_i$。负责人需要将他们按照原顺序分成若干个连续小组，每名志愿者必须恰好属于一个小组。

一个小组合法，当且仅当人数不少于 $L$ 且不超过 $R$，并且组内能力值最大值与最小值之差不超过 $K$。

请你求出合法分组方案数，对 $10^9+7$ 取模后输出。

输入格式

第一行四个整数 $n,L,R,K$。第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示合法方案数模 $10^9+7$ 的结果。

样例输入

5 1 3 2
1 2 3 5 4

样例输出

12

样例解释

例如 [1] [2] [3] [5] [4]、[1 2] [3] [5 4]、[1 2 3] [5 4] 均为合法方案。合法方案总数为 $12$。

数据范围

• $1 \le L \le R \le n \le 2\times 10^5$；
• $0 \le K \le 10^9$；
• $0 \le a_i \le 10^9$。