Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-07-30 20:16:00.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:antocod.in, antocod.outSursăInfoarena Monthly 2014, Runda 7
AutorIulia Duta, Teodor PlopAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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 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.

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

Exemplu

antocod.inantocod.out
2
3
2 3 3
64

Explicaţie

Pentru simplitatea explicaţiei, vom nota prima valoare de 3 din şir cu 3_1, iar cea de-a doua cu 3_2. Vom avea configuraţiile:
(2, 2), având un total de 4;
(2, 3_1), (2, 3_2), (3_1, 2), (3_2, 2), având un total de 24;
(3_1, 3_1), (3_1, 3_2), (3_2, 3_1), (3_2, 3_2), având un total de 36.

În total, vom avea: 4 + 24 + 36 = 64.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?