| Fişierul intrare/ieşire: | antocod.in, antocod.out | Sursă | Infoarena Monthly 2014, Runda 7 |
| Autor | Iulia Duta, Teodor Plop | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Antocod
Antonia este o fetiţă hiperactivă. Pentru a-şi ţine fiica ocupată, Antonela, mama Antoniei, i-a oferit acesteia un cifru format din N căsuţe şi o listă cu M numere distincte pe care le poate introduce în căsuţe (un număr poate fi introdus în mai multe căsuţe). Pentru o configuraţie a cifrului Antonela a numit antocod numărul format prin înmultirea numerelor din cele N căsuţe care intră în alcătuirea cifrului.
Antonela i-a cerut fiicei sale să determine suma antocodurilor tuturor configuraţiilor posibile, modulo 666013. Pentru că este prea ocupată să îi preagătească aniversarea fiicei sale, nu are timp sa facă calculele aşa că vă roagă pe voi să îi spuneţi răspunsul pentru a putea verifica dacă fiica sa a răspuns corect.
Două configuraţii V1 şi V2 ale cifrului se consideră diferite dacă există cel puţin o căsuţă i (1 ≤ i ≤ N), pentru care V1[i] != V2[i].
Date de intrare
Fişierul de intrare antocod.in conţine pe prima linie se vor găsi două numere naturale N şi M cu semnificaţia din enunţ, iar pe următoarea linie M numere naturale reprezentând numerele ce se pot regăsi în căsuţele cifrului.
Date de ieşire
În fişierul de ieşire antocod.out se va găsi un singur număr natural, reprezentând răspunsul întrebării puse de Antonela, modulo 666013.
Restricţii
- 1 ≤ N ≤ 109
- 1 ≤ M ≤ 105
- 1 ≤ X ≤ 109, unde X este un număr din lista pe care Antonela i-a oferit-o Antoniei.
- Cele M numere sunt distincte două câte două.
Exemplu
| antocod.in | antocod.out |
|---|---|
| 2 3 2 3 1 | 36 |
Explicaţie
Avem configuraţiile:
(2, 2), având un total de 4;
(2, 3), (2, 1), (3, 2), (1, 2), având un total de 16;
(3, 3), (3, 1), (1, 3), (1, 1), având un total de 16.
În total, vom avea: 4 + 16 + 16 = 36.
