== include(page="template/taskheader" task_id="plangaciosi") ==
De 1 iunie, _Doamna Eraotacude_ s-a gândit să le organizeze celor $K$ copii de la grădiniţă o surpriză. Ea a cumpărat $N$ torturi, tortul cu numărul $i$ având $A{~i~}$ felii. Ea a aranjat copiii într-un şir, i-a numerotat de la $1$ la $K$ (se garantează că ştie să numere până la $K$) şi după o gândire îndelungată a hotărât cum să împartă dulciurile. Astfel, la fiecare moment de timp, copilul care este primul din rând se va apropia de masa pe care sunt aşezate torturile şi va spune din care tort şi-ar dori sa mănânce.
De 1 iunie, $Doamna Eraotacude$ s-a gândit să le organizeze celor $K$ copii de la grădiniţă o surpriză. Ea a cumpărat $N$ torturi, tortul cu numărul $i$ având $A{~i~}$ felii. Ea a aranjat copiii într-un şir, i-a numerotat de la $1$ la $K$ (se garantează că ştie să numere până la $K$) şi după o gândire îndelungată a hotărât cum să împartă dulciurile. Astfel, la fiecare moment de timp, copilul care este primul din rând se va apropia de masa pe care sunt aşezate torturile şi va spune din care tort şi-ar dori să mănânce.
* Dacă pe masă se afla cel puţin o felie din tortul respectiv, _Doamna Eraotacude_ îi va da micuţului o felie din acel tort, iar micuţul se va aseza fericit la coada rândului.
* Dacă pe masă se află cel puţin o felie din tortul respectiv, $Doamna Eraotacude$ îi va da micuţului o felie din acel tort, iar micuţul se va aşeza fericit la coada rândului.
* Altfel, dacă pe masă nu se mai află nicio felie din tortul respectiv, micuţul va începe să plângă, drept pentru care va fi numit _PlângăciosulNr1_. Bineînţeles, într-o fracţiune de secundă, colegii lui îl vor urma, declanşând astfel _Corul de Plângăcioşi_. În acel moment, _Doamna Eraotacude_ va opri definitiv servirea dulciurilor şi va încerca să oprească _Corul de Plângăcioşi_. Pentru a face acest lucru, ea trebuie sa îl pună la colţ pe _PlângăciosulNr1_.
* Altfel, dacă pe masă nu se mai află nicio felie din tortul respectiv, micuţul va începe să plângă, drept pentru care va fi numit $PlângăciosulNr1$. Bineînţeles, într-o fracţiune de secundă, colegii lui îl vor urma, declanşând astfel $Corul de Plângăcioşi$. În acel moment, $Doamna Eraotacude$ va opri definitiv servirea dulciurilor şi va încerca să oprească $Corul de Plângăcioşi$. Pentru a face acest lucru, ea trebuie sa îl pună la colţ pe $PlângăciosulNr1$.
Din motive pur statistice, _Doamna Eraotacude_ vrea să ştie, pentru fiecare copil, pentru câte secvenţe de alegeri va ajunge acel copil să fie _PlângăciosulNr1_. O secvenţă $s{~1~}$, $s{~2~}$, $s{~3~}$, ..., $s{~p~}$ se numeşte secvenţă de alegeri dacă $s{~t~}$ reprezintă tortul din care s-a luat felia de la momentul t ({$1≤t≤p-1$}), iar $s{~p~}$ reprezintă tortul din care ar fi vrut să mănânce _PlângăciosulNr1_. Evident, pentru ca o secvenţă de alegeri să fie validă, este necesar ca la momentul $t$ ({$1≤t≤p-1$}) să existe pe masă cel puţin o felie din tortul $s{~t~}$, iar la momentul $p$ să nu mai existe pe masă nicio felie din tortul $s{~p~}$.
Din motive pur statistice, $Doamna Eraotacude$ vrea să ştie, pentru fiecare copil, pentru câte secvenţe de alegeri va ajunge acel copil să fie $PlângăciosulNr1$. O secvenţă $s{~1~}$, $s{~2~}$, $s{~3~}$, ..., $s{~p~}$ se numeşte secvenţă de alegeri dacă $s{~t~}$ reprezintă tortul din care s-a luat felia de la momentul t ({$1≤t≤p-1$}), iar $s{~p~}$ reprezintă tortul din care ar fi vrut să mănânce $PlângăciosulNr1$. Evident, pentru ca o secvenţă de alegeri să fie validă, este necesar ca la momentul $t$ ({$1≤t≤p-1$}) să existe pe masă cel puţin o felie din tortul $s{~t~}$, iar la momentul $p$ să nu mai existe pe masă nicio felie din tortul $s{~p~}$.
h2. Date de intrare
Fişierul de intrare $plangaciosi.in$
Fişierul de intrare $plangaciosi.in$ va conţine pe prima linie $N$ şi $K$. Pe cea de-a doua linie se vor găsi cele $N$ valori $A{~i~}$.
h2. Date de ieşire
În fişierul de ieşire $plangaciosi.out$ ...
Fişierul de ieşire $plangaciosi.out$ va conţine o singură linie cu $K$ valori. Cea de-a $i$-a valoare va reprezenta numărul de secvenţe de alegeri în care copilul $i$ este $PlângăciosulNr1$ (modulo $1.000.000.007$).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, K ≤ 2000$
* $1 ≤ A{~i~} ≤ 2000$
* $A{~1~} + A{~2~} + A{~3~} + ... + A{~N~} ≤ 2000$
* Pentru 10 puncte, se garantează că în total sunt cel mult $2 * 10^6^$ de secvenţe de alegeri
* Pentru alte 10 puncte, se garantează că $A{~i~} = 1$, pentru orice $i$
* Pentru alte 30 de puncte, se garantează că $N ≤ 40$ şi $A{~1~} + A{~2~} + A{~3~} + ... + A{~N~} ≤ 400$
* Pentru alte 25 de puncte, se garantează că $A{~1~} + A{~2~} + A{~3~} + ... + A{~N~} ≤ 800$
h2. Exemplu
