Zoo

문제

Esmeralda bygger ett zoo med $NN$ burar i en lång rad. Varje bur ska fyllas med ett djur. Hon har $KK$ olika djurarter att välja på, som vi kallar A, B, C, o.s.v. Hon kan ha flera burar med samma djurart, men inte precis intill varandra. Dessutom vet hon att vissa djur inte trivs bra ihop. Närmare bestämt så finns det $MM$ stycken "bråkiga grupper" av djurarter, och Esmeralda vill inte placera två djur ur samma bråkiga grupp i burar intill varandra. På hur många sätt kan Esmeralda placera ut djur i burarna?

입력

Den första raden innehåller tre heltal: $2\le N\le 152\backslash le\; N\; \backslash le\; 15$, antalet deltagare, $2\le K\le 102\backslash le\; K\; \backslash le\; 10$, antalet djurarter, och $2\le M\le 52\; \backslash le\; M\backslash le\; 5$, antalet bråkiga grupper. På var och en av de följande $MM$ raderna står en sträng som består av mellan $22$ och $KK$ bokstäver: en bråkig grupp av djurarter som parvis inte tolererar varandra. Endast de $KK$ första bokstäverna i alfabetet (och endast versaler) kan förekomma i strängarna och en bokstav förekommer inte flera gånger i samma sträng.

출력

Programmet ska skriva ut ett heltal, antal sätt Esmeralda kan placera ut djur på. För givna indata kommer svaret aldrig överstiga 2 miljarder.

힌트

I det första exemplet trivs alla arter ihop. I första buren kan Esmeralda välja mellan 4 djurarter. För andra och tredje buren finns tre möjligheter vardera, eftersom det inte får vara samma art som i den föregående. Totalt finns $4\cdot 3\cdot 3=364\backslash cdot\; 3\backslash cdot\; 3=36$ möjliga placeringar.

I det andra exemplet vet vi att Babian och Elefant inte får vara intill varandra. Vi vet också att Babian, Antilop, Dingo och Citronfjäril alla är fiender, och inga av dessa kan därför sättas intill varandra. Esmeralda måste sålunda sätta en elefant i varannan bur och välja fritt mellan antilop, dingo och citronfjäril i de övriga. Detta ger 9 möjligheter om hon börjar med elefant och 9 möjligheter om hon börjar med något av de andra djuren.