antocod

Antocod

== include(page="template/taskheader" task_id="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 in căsuţe (un număr poate fi introdus în mai multe căsuţe).

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.

Pentru o configuraţie a cifrului Antonela a numit antocod numărul format din înmultirea celor $n$ numere care intra in alcătuirea configuraţiei şi i-a cerut fiicei sale să determine suma antocodurilor tuturor configuraţiilor posibile, modulo $666 013$. 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 raspuns corect.

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]$.

h2. Date de intrare

Fişierul de intrare $antocod.in$ conţine pe prima linie un numar natural reprezentând numărul de teste. Pentru fiecare test, pe prima linie se vor găsi doua 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.

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.

h2. Date de ieşire

În fişierul de ieşire $antocod.out$ se vor găsi $T$ linii, pe fiecare linie $i$ aflându-se un numar natural, răspunsul la întrebarea $i$.

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10^9^$
* $1 ≤ M ≤ 10^5^$
* $1 ≤ X ≤ 10^9^, 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ă.$

h2. Exemplu
table(example). |_. antocod.in |_. antocod.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 3
2 3 1
| 36

|
h3. 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$.

== include(page="template/taskfooter" task_id="antocod") ==

10107