Estênceis equilibrados
Um molde quadrado tem linhas e colunas. Cada célula está marcada com # ou .. Você pode pintar de preto qualquer subconjunto das células marcadas com #; as demais células, incluindo todas as marcadas com ., permanecem brancas.
Uma pintura é equilibrada quando cada linha e cada coluna contém uma quantidade par de células pretas. Zero é uma quantidade par.
Considere as oito operações geométricas do quadrado: rotações de , , e graus e reflexões nos eixos horizontal, vertical e nas duas diagonais. Uma operação é permitida somente quando preserva o molde inteiro: ela deve levar cada célula # a outra célula # e cada célula . a outra célula ..
Duas pinturas equilibradas são equivalentes se uma operação permitida transforma uma na outra. Essa permissão depende do molde, mesmo quando algumas células # não foram pintadas. Não são permitidos deslocamentos, permutações arbitrárias de linhas ou colunas, nem trocas de preto por branco.
Quantas pinturas equilibradas diferentes existem, módulo ?
Input
A primeira linha contém o inteiro . As próximas linhas contêm, cada uma, caracteres # ou ., descrevendo o molde.
- .
Output
Um inteiro: a quantidade de classes de equivalência de pinturas equilibradas, módulo .
Samples
Sample 1
Input
2 ## ##
Output
2
As únicas pinturas equilibradas são a inteiramente branca e a inteiramente preta.
Sample 2
Input
2 #. .#
Output
1
Nenhuma célula pode ser preta sem criar uma linha com quantidade ímpar de células pretas.
Sample 3
Input
3 ### ### ###
Output
6