7. Obávaný skok syslí, horizontálno-zvislý

Počuli ste už o paraglidingu? Je to rekreačno-adrenalínový šport v štýle ‘riadeného voľného pádu’ – inak povedané, po skoku z vyvýšeného miesta sa s pomocou vyčačkaného padáka vznášate nad okolitou krajinou, pričom vás gravitácia pomaly, ale neúprosne priťahuje k zemi.

Paragliding, ako každý správny šport, má svoj klub nadšencov s neoriginálnym názvom – Klub Slovenských Paraglidistov (KSP). A ako každý správny zväz organizuje KSP klubové akcie – spoločné výlety do prestížnych paraglidingových centier, kde sa členovia klubu do sýtosti vylietavajú v tých najlukratívnejších pohoriach. Samozrejme, každá akcia musí byť úžasnejšia ako tá predošlá, a preto je výber správnej destinácie kľúčový. Tento rok sa dokonca na akciu prihlásila legenda Tatranského paraglidingu Syseľ Samovrah. Ten je svojou vytrvalosťou a zápalom pre tento šport známy na svetovej paraglidingovej scéne.

V jeho bestseller autobiografii sa členovia KSP dočítali, že Syseľ si najviac užíva veľké zoskoky – také, kde prevýšenie, ktoré preletí, je väčšie ako \(m\). V rámci exkluzívneho rozhovoru tiež spomenul, že na paraglidingu mu najviac prekáža nutnosť po každom skoku vyšliapať naspäť na kopec. Preto väčšinou skočí z vrchola jedného kopca a pristane na vrchole nejakého nižšieho, z ktorého môže opäť skočiť ďalej. Ak toto urobí \(s-1\) krát, už mu v porovnaní s počtom skokov výstup na prvý kopec až tak neprekáža. No a z odpočutého telefónneho rozhovoru vysvitlo, že Syseľ rád lietava po dobrom obede, ale zásadne smerom na východ, keďže pri lete na západ by mu svietilo slnko do očí.

KSP nechce Sysľa na svojej akcii sklamať, a preto hľadá také pohorie, ktoré obsahuje najviac trás vyhovujúcich Sysľovi. Napíšte program, ktorý im v tom pomôže.

Úloha

Každé pohorie s \(n\) horami sa dá opísať ako postupnosť \(n\) čísel, reprezentujúcich výšky hôr v ňom, v smere od západu na východ. Trasa je ľubovolná postupnosť niekoľkých, nie nutne susediacich hôr, pričom Sysľovi vyhovuje práve vtedy, ak obsahuje presne \(s\) hôr takých, že medzi každou za sebou idúcou dvojicou hôr je prevýšenie väčšie ako \(m\) – teda ak výška západnejšej hory je \(x\) a výška východnejšej hory je \(y\), tak musí platiť, že \(x-y > m\). Pre dané pohorie tvorené \(n\) horami a hodnoty \(m\) a \(s\) nájdite počet trás, ktoré vyhovujú Sysľovym požiadavkam.

Formát vstupu

Na prvom riadku sú tri čísla \(n\), \(m\) a \(s\) (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^{18}\), \(2 \leq s \leq 20\)) – počet hôr v pohorí, najmenšie prevýšenie ktoré Sysľa uspokojí, a počet hôr v trase, ktorá mu vyhovuje.

V druhom riadku je \(n\) čísiel \(h_{i}\) ( \(1 \leq h_{i} \leq 10^{18}\)) – výšky hôr v pohorí, od západu na východ.

Navyše pre jednotlivé vstupné sady platí

Formát výstupu

Vypíšte jedno číslo – počet rôznych trás, ktoré obsahujú presne \(s\) hôr a každá hora na trase je o viac ako \(m\) vyššia od tej nasledujúcej. Dve trasy považujeme za rôzne, ak existuje aspoň jedna hora, ktorá patrí do jednej z nich, ale nie do druhej.

Keďže toto číslo môže byť príliš veľké, pre KSP stačí vedieť tento počet modulo \(1\,000\,000\,007\) (\(10^9+7\)).

Príklad

Input:

4 0 2
5 4 3 1

Output:

6

Sysľovi vyhovuje ľubovoľná dvojica hôr.

Input:

4 1 2
5 4 3 1

Output:

4

Sysľovi už nevyhovujú dvojice \((5,4)\) a \((4,3)\)

Input:

8 3 3
11 15 15 10 10 7 1 1

Output:

14