Fişierul intrare/ieşire:	nrcuv.in, nrcuv.out	Sursă	preONI 2006 Runda 4
Autor	Daniel Pasaila	Adăugată de
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Lista lui Andrei

Fiind foarte pasionat de civilizatiile extraterestre, Andrei a inceput sa studieze limba martienilor pentru a putea comunica usor cu ei atunci cand va fi cazul. Oricat s-a documentat el a putut afla doar ca toate cuvintele acestei limbi contin N litere mici din alfabetul englez si a mai gasit o lista cu perechi de litere ce nu pot aparea pe pozitii vecine intr-un cuvant. Pentru ca are de gand sa studieze fonetica fiecarui cuvant posibil in parte, Andrei ar vrea mai intai sa vada cat de voluminoasa este munca pe care si-o propune si va roaga sa determinati cate cuvinte poate avea limba.

Cerinta

Determinati cate cuvinte de lungime N se pot forma folosind doar litere mici ale alfabetului englez astfel incat oricare doua litere care formeaza o pereche in lista lui Andrei sa nu se afle pe pozitii vecine.

Date de intrare

Pe prima linie a fisierului nrcuv.in se afla numerele intregi N si M, reprezentand numarul de litere din care este format un cuvant si numarul de perechi din lista lui Andrei. Urmatoarele M linii contin o pereche de forma "l₁ l₂" unde l₁ si l₂ sunt litere mici ale alfabetului englez.

Date de iesire

Fisierul nrcuv.out contine pe prima linie numarul cerut modulo 104659.

Restrictii si precizari

• 1 ≤ N ≤ 1000
• 0 ≤ M ≤ 2000
• Pot exista perechi simetrice sau identice in lista
• Doua pozitii sunt vecine daca modulul diferentei lor este 1

Exemplu

Cum se trimit solutii?