== 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(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.

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.

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$.

* $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

h2. Exemplu