| Fişierul intrare/ieşire: | icrisop.in, icrisop.out | Sursă | ad-hoc |
| Autor | Alexandru Tache | Adăugată de |  Ionut Bogdanescu •swift90 |
| Timp execuţie pe test | 0.7 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
Date de intrare
Fisierul de intrare icrisop.in contine pe prima linie N si S, iar pe urmatoarele N linii cate un numar reprezentand gradul de magie al fiecarui tip de icrisop.
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.
Restricţii
- 1 ≤ N ≤ 30 000
- 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
Exemplu
| icrisop.in | icrisop.out |
|---|---|
| 3 2 1 2 1 | 5 |
Explicaţie
Urmatoarele combinatii sunt posibile: tip1+tip1, tip3+tip3, tip1+tip3, tip3+tip1, tip2
