Fişierul intrare/ieşire:pokemon2.in, pokemon2.outSursăJunior Challenge 2012
AutorRadu Stefan VoroneanuAdăugată dejuniorcJunior Challenge juniorc
Timp execuţie pe test0.075 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/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 A1, diferenta intre levelul celui de-al doilea pokemon si levelul celui de-al treilea pokemon sa fie cel putin A2 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 Ai 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 ≤ Ai ≤ 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

pokemon2.inpokemon2.out
3 5
1 1
2

Explicaţie

Solutiile sunt 3 2 0 si 4 1 0.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?