Fişierul intrare/ieşire:	plangaciosi.in, plangaciosi.out	Sursă	Junior Challenge 2020
Autor	Alexa Tudose	Adăugată de	Comisia •JuniorChallenge2020
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 să mănânce.

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

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₁, s₂, s₃, ..., 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.

Date de intrare

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.

Date de ieşire

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

Restricţii

• 1 ≤ N, K ≤ 2000
• 1 ≤ A_i ≤ 2000
• A₁ + A₂ + A₃ + ... + A_N ≤ 2000
• Pentru 10 puncte, se garantează că în total sunt cel mult 2 * 10⁶ 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₁ + A₂ + A₃ + ... + A_N ≤ 400
• Pentru alte 25 de puncte, se garantează că A₁ + A₂ + A₃ + ... + A_N ≤ 800

Exemplu

Explicaţie

Cele 10 secvenţe de alegeri sunt:

1. 1 1
2. 1 2 1
3. 1 2 2 1
4. 1 2 2 2
5. 2 1 1
6. 2 1 2 1
7. 2 1 2 2
8. 2 2 1 1
9. 2 2 1 2
10. 2 2 2

PlângăciosulNr1 este copilul 2 în prima secvenţă, copilul 3 în secvenţele 2, 5 şi 10, şi copilul 4 în celelalte 6 secvenţe.

Cum se trimit solutii?