Fişierul intrare/ieşire:	arduino.in, arduino.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 17
Autor	Florin Chirica	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Arduino

Niramax isi face bradutul anul acesta impreuna cu colegii sai de munca. Echipa deja a impodobit bradul cu globulete in timp ce ascultau "Impodobeste mapa bradul", un faimos slagar. Tot ce mai ramane de facut este sa fie puse becurile.

Becurile alese sunt date printr-un vector cu N elemente, fiecare element reprezentand un beculet. Fiecare beculet poate lua M culori. Intrebarea ce macina echipa este cum sa aleaga culorile beculetelor. Un bicsan, fiind cel mai tare in gura de acolo, se impune prin urmatoarea schema:
"Nu mai fiti penali! Frumusetea e data de numarul de culori diferite din instalatie. Putem pune restrictii asupra numarului de culori distincte. Ca sa fie distribuite frumos culorile, va dau R restrictii de forma:

- NR K i₁ i₂ ... i_K: Luam valorile din vector de pe pozitiile i₁ i₂ ... i_K. Aceste valori trebuie sa contina fix NR numere distincte dupa ce eliminam dublurile."

Imediat ce bicsanul a terminat de insirat restrictiile in timp ce toti se uitau uimiti la el, inamicul sau numarul 1 de la munca ii spune ca e greu de gasit o solutie. Bicsanul ii raspune "ba nu, esti penal, haha! ti le gasesc chiar pe toate. chiar acum ma duc sa codez". Niramax ii spune bicsanului "bicsane, nu e nevoie sa faci asta", dar era prea tarziu. Bicsanul era deja in lumea sa.

Treaba voastra e sa calculati numarul gasit de bicsan.

Date de intrare

Fişierul de intrare arduino.in va contine pe prima linie numerele N M si pe cea de-a doua linie numarul de restrictii R. Urmatoarele R linii contin descrierile restrictiilor NR K i₁ i₂ ... i_K, cate una pe linie.

Date de ieşire

În fişierul de ieşire arduino.out se va afisa pe o singura linie raspunsul.

Restricţii

• 2 ≤ N ≤ 10
• 1 ≤ M ≤ 1000
• 1 ≤ suma K-urilor ≤ 100
• WEEEEE!
• ATENTIE!!! Se cere afisarea raspunsului MODULO 10⁹+7

Exemplu

Explicaţie

Face overflow varsta noastra pana cand numaram babeste raspunsul...

Cum se trimit solutii?