Bilda ord

Fatimeh studerar sitt hemspråk som använder det arabiska alfabetet. Just nu sitter hon med en övning där hon ska svara på hur många sätt hon kan bilda ett ord med de givna bokstäverna i uppgiften.

Om det hade varit på svenska kunde övningen ha se ut så här:

Eftersom fyra bokstäver är givna vet Fatimeh att hon måste testa $4*3*2*1 = 24$ permutationer. Men eftersom bokstaven M är “stor” så vet vi att den måste placeras i ordets början. Med det villkoret kan bara $6$ ord bildas, exempelvis $Mera$, men inte $raMe$. I det arabiska alfabetet har man inte stora och små bokstäver på samma sätt, men man har andra regler om var i ordet bokstaven kan förekomma, även i relation till andra bokstäver.

I denna uppgift antar vi att det finns två typer av restriktioner: Antingen måste en bokstav komma precis före någon annan bokstav, eller så kan en bokstav bara stå på vissa positioner. Exempel på dessa regler och den notation vi använder finns i följande tabell:

Skriv ett program som beräknar på hur många sätt som $N$ olika bokstäver (för enkelhets skull kallade A, B, C,... etc.) kan placeras ut, givet ett antal regler av dessa två typer.

Indata

På första raden står två heltal, antalet bokstäver $N$ och antalet regler $K$. Därefter följer $K$ rader vardera beskrivande en regel enligt notationen ovan. En viss bokstav kan inte stå först i mer än en regel av vardera typen. Observera att alla platsnummer skrivs med två siffror.

Utdata

Programmet ska skriva ut ett heltal: antalet sätt bokstäverna kan placeras ut. Svaret kommer alltid att understiga 10 miljoner.

Poängsättning

För testfall värda $60$ poäng gäller att $2\le N\le 9$. För full poäng så ska ditt program klara $2\le N\le 15$. I samtliga fall gäller att $1\le K\le N$. För stora $N$ kommer restriktionerna vara ungefär jämnt utspridda bland bokstäverna.

Förklaring till exempel 1

De ord som kan bildas är ACDB, ADCB, BADC, CADB, DCAB och BDCA.

4 2
B@01,04
D:CB

6

3 2
B@02
A:BC

1

3 2
B@02
A:C

0

8 4
E@02,08,05
A:CEF
A@05,02,03
C:ABCDH

918