== include(page="template/taskheader" task_id="pokemon2") ==

Toti stim povestea lui Ash in legendara lume pokemon. De data aceasta Ash vrea sa participe la turneul final pentru a deveni cel mai mare maestru pokemon. El dispune de $N$ pokemoni. La inscrierea in competitie a descoperit o regula ciudata : niciun pokemon nu are voie sa creasca in level pe parcursul turneului. De aceea baiatul nostru s-a gandit ca este mai bine sa isi creasca cat mai mult posibil pokemonii inainte de inscriere. Pentru aceasta el dispune de $M$ Rare candy. Un Rare candy este un item care are capacitatea de a mari levelul unui pokemon cu $1$, iar un pokemon poate manca oricate astfel de dulciuri. Ash are o lista de preferinte intre pokemoni si doreste ca la final, diferenta intre levelul primului pokemon si levelul celui de-al doilea pokemon sa fie cel putin $A{~1~}$, diferenta intre levelul celui de-al doilea pokemon si levelul celui de-al treilea pokemon sa fie $A{~2~}$ si asa mai departe.

Toti stim povestea lui Ash in legendara lume pokemon. De data aceasta Ash vrea sa participe la turneul final pentru a deveni cel mai mare maestru pokemon. El dispune de $N$ pokemoni. La inscrierea in competitie a descoperit o regula ciudata : niciun pokemon nu are voie sa creasca in level pe parcursul turneului. De aceea baiatul nostru s-a gandit ca este mai bine sa isi creasca cat mai mult posibil pokemonii inainte de inscriere. Pentru aceasta el dispune de $M$ Rare Candy. Un Rare Candy este un item care are capacitatea de a mari levelul unui pokemon cu $1$, iar un pokemon poate manca oricate astfel de dulciuri. Ash are o lista de preferinte intre pokemoni si doreste ca la final, diferenta intre levelul primului pokemon si levelul celui de-al doilea pokemon sa fie cel putin $A{~1~}$, diferenta intre levelul celui de-al doilea pokemon si levelul celui de-al treilea pokemon sa fie cel putin $A{~2~}$ si asa mai departe.

Ash doreste sa stie in cate moduri poate sa imparta Rare candy-urile pokemonilor astfel incat sa se respecte preferintele lui. Deoarece rezultatul poate ajunge foarte mare sa se afiseze rezultatul $modulo 1000000007$.

Ash doreste sa stie in cate moduri poate sa imparta Rare Candy-urile pokemonilor astfel incat sa se respecte preferintele lui. Deoarece rezultatul poate ajunge foarte mare sa se afiseze rezultatul $modulo 1000000007$.

h2. Date de intrare

Fişierul de intrare $pokemon2.in$ va contine doua numere naturale $N$, $M$ reprezentand numarul de pokemoni, respectiv numarul de Rare candy-uri pe care Ash le detine. Pe urmatoarea linie sunt scrise $N-1$ numere naturale, al $i$-lea numar reprezentand $A{~i~}$ si anume diferenta minima ceruta intre levelul celui de-al $i$-lea pokemon si levelul celui de-al $i+1$-lea pokemon.

Fişierul de intrare $pokemon2.in$ va contine doua numere naturale $N$, $M$ reprezentand numarul de pokemoni, respectiv numarul de Rare Candy-uri pe care Ash le detine. Pe urmatoarea linie sunt scrise $N-1$ numere naturale, al $i$-lea numar reprezentand $A{~i~}$ si anume diferenta minima ceruta intre levelul celui de-al $i$-lea pokemon si levelul celui de-al $i+1$-lea pokemon.

h2. Date de ieşire

h3. Explicaţie

Solutile sunt $3 2 0$ si $4 1 0$.

Solutiile sunt $3 2 0$ si $4 1 0$.

== include(page="template/taskfooter" task_id="pokemon2") ==