icrisop

Icrisop

== include(page="template/taskheader" task_id="icrisop") ==

Intr-un tinut indepartat, Regele Spiderman incearca din rasputeri sa creeze icrisopul magic. El are la dispozitie N tipuri de icrisop fiecare cu un anumit grad de magie, pana in 100. Pentru a obtine icrisopul magic el trebuie sa combine icrosupurile intr-o anumita ordine astfel incat suma gradelor de magie sa fie fix S. Regele Spiderman va cere sa aflati in cate moduri se poate obtine icrisopul de gradul magic S, modulo $666013$, considerand ca exista un numar nelimitat  de icrisop din fiecare tip si ca ordinea in care sunt adaugate icrosopurile conteaza. De exemplu pentru $S=2$, $N=3$ si tipurile de icrisop cu gradul de magie $1, 1, 2$ raspunsul este $5$ (tip1 + tip1, tip1 + tip 2, tip 2 + tip 1, tip 2 + tip 2, tip 3).

Intr-un tinut indepartat, Regele Spiderman incearca din rasputeri sa creeze icrisopul magic. El are la dispozitie $N$ tipuri de icrisop fiecare cu un anumit grad de magie, pana in $100$. Pentru a obtine icrisopul magic el trebuie sa combine icrosupurile intr-o anumita ordine astfel incat suma gradelor de magie sa fie fix $S$. Regele Spiderman va cere sa aflati in cate moduri se poate obtine icrisopul de gradul magic $S$, modulo $666013$, considerand ca exista un numar nelimitat  de icrisop din fiecare tip si ca ordinea in care sunt adaugate icrosopurile conteaza. De exemplu pentru $S = 2$, $N = 3$ si tipurile de icrisop cu gradul de magie $1,1,2$ raspunsul este $5$ (tip1 + tip1, tip1 + tip 2, tip 2 + tip 1, tip 2 + tip 2, tip 3).

h2. Date de intrare

h2. Date de ieşire

In fisierul de iesire $icrisop.out$ veti afisa numarul de moduri in care se poate forma icrisopul magic( de magie $S$ ) modulo $666013$.

In fisierul de iesire $icrisop.out$ veti afisa numarul de moduri in care se poate forma icrisopul magic, de magie $S$, modulo $666013$.

h2. Restricţii
* $1 ≤ N ≤ 30 000$

* $1 ≤$ Gradul de magie al oricarui icrisop $≤ 100$

* $1 ≤ gradul de magie al oricarui icrisop ≤ 100$

* $S$ incape pe un intreg de $32$ de biti cu semn.
* Pentru $20%$ din teste $S ≤ 100000$

5932