Problem C
Kodlås

Åskold har just köpt ett nytt kodlås. Försäljaren lovade att låset är mycket säkert, men Åskold är inte övertygad. Därför vill han att du ska räkna ut hur många olika kombinationer som öppnar låset.

Kodlåset består av $N$ intilliggande skivor. Varje skiva har $M$ segment, där ett segment antingen är ifyllt eller ett hål. För att skriva in en kod vrider man på skivorna. Varje skiva kan sättas i $M$ olika lägen, eftersom mekanismen inte tillåter att du vrider skivan mindre än ett helt segment. Låset öppnas om det någonstans går ett hål genom alla skivor på samma ställe.

Vi kan beskriva varje skiva som en sträng bestående av "." och "#", där "." representerar ett segment med hål i och "#" representerar ett ifyllt segment. Att rotera en skiva ett steg kan då ses som att ta sista tecknet i strängen och lägga det i början. Om skivan roteras $M$ steg kommer den tillbaka till läget den började i.

Exempelvis kan skivan ".#..#" ställas in i följande 5 lägen

Totalt finns det alltså $M^ N$ möjliga sätt att ställa in de $N$ skivorna, och låset öppnas ifall någon kolumn bara består av "." när man skriver ut alla skivornas strängar ovanför varandra. Skriv ett program som beräknar hur många sätt det finns att ställa in skivorna så att låset öppnas.

Indata

Ditt program ska först läsa in två heltal: $N$ ($1\le N \le 12$) – antal skivor och $M$ ($1\le M \le 12$) – antal segment.

Därefter ska ditt program läsa in beskrivningar av de $N$ skivorna. Varje skiva beskrivs av en rad med $M$ tecken bestående av "." och "#".

Utdata

Ditt program ska skriva ut ett heltal: antalet sätt man kan ställa in skivorna så att låset öppnas.

Poängsättning

För 2 poäng gäller det att $M,N \le 5$.
För ytterligare 1 poäng gäller det att $N \le 8, M\le 10$ och att det finns max 3 hål i varje skiva.
För de sista 2 poängen gäller det att $M,N \le 12$.

Förklaring av exempel

• I det första exempelfallet öppnar alla de nio inställningarna av skivorna låset.

• I det andra exempelfallet öppnar ingen inställning av skivorna låset, då den andra skivan inte har några hål.

• I det tredje exempelfallet öppnar följande två inställningar låset:

  .#			#.
  .#			#.
  .#			#.

• I det fjärde exempelfallet finns det tre (av de nio möjliga) inställningar som inte öppnar låset: då "." i det andra skivan är precis under "#" i den första skivan.

Exempelfall

2 3
.#.
#..

9

3 4
..#.
####
..#.

0

3 2
#.
.#
#.

2

2 3
..#
.##

6