20880번 - 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:

r M e a

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. 

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.

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

• $2\le N\le 15$