== 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 codului ş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.

*Mihai: Aici trebuie să definiţi ce înseamnă două antocoduri diferite. Probabil se diferenţiază în funcţie de indicii pe care îi folosiţi în configuraţie, fiindcă dacă ar fi să fie după valori pare cam nasol.*

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 writte
| 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