203016 - 分割方案

一个长度为n的数组a,你需要将a分割成1段或者多段非空连续子段,使得每个子段的最大值-最小值不超过k,求总的分割方案是多少。

输入

第一行为一个整数n(1≤n≤10^6)和k(0 ≤≤10^9)。 第二行为n个整数a[i](0≤a[i]≤10^9)。

输出

输出总的分割方案数。由于答案可能非常大,返回结果需要对109+7取余数。

样例

输入

5 4
9 4 1 3 7

输出

6
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题