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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content