pokemon2

Pokemon2

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

Poveste şi cerinţă...

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(inca o data). 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.
 
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$ ...

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

În fişierul de ieşire $pokemon2.out$ ...

În fişierul de ieşire $pokemon2.out$ va contine un singur reprezentand numarul de moduri de a imparti Rare Candy-urile $modulo 1000000007$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100$
* $0 ≤ A{~i~} ≤ 10$
* $1 ≤ M ≤ 100 000$
* $a modulo b$ reprezinta restul impartirii lui $a$ la $b$
* Un mod de impartire difera de altul daca exista un pokemon a carui level final difera in cele doua situatii.

h2. Exemplu
table(example). |_. pokemon2.in |_. pokemon2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 5
1 1
|2

|
h3. Explicaţie

...

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

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