Fişierul intrare/ieşire:	pokemon2.in, pokemon2.out	Sursă	Junior Challenge 2012
Autor	Radu Stefan Voroneanu	Adăugată de	Junior Challenge •juniorc
Timp execuţie pe test	0.075 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁, diferenta intre levelul celui de-al doilea pokemon si levelul celui de-al treilea pokemon sa fie cel putin A₂ 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.

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.

Date de ieşire

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

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.
• Initial level-urile pokemonilor sunt 0

Exemplu

Explicaţie

Solutiile sunt 3 2 0 si 4 1 0.

Cum se trimit solutii?