Agendas que se repetem
Uma equipe usa uma agenda cíclica com dias. Em cada dia, escolhe uma entre atividades, numeradas de a . As atividades têm nomes distintos, que não podem ser permutados.
Uma matriz binária determina as transições permitidas: uma atividade pode ser seguida imediatamente pela atividade se, e somente se, . Essa regra também vale entre o último dia e o primeiro. A matriz não precisa ser simétrica, e uma atividade só pode ser seguida por ela mesma quando a entrada correspondente da diagonal é .
Duas agendas válidas são equivalentes se uma é um deslocamento cíclico da outra. A ordem dos dias não pode ser invertida. A agenda tem exatamente posições, mas pode repetir um bloco menor; não é necessário que seja seu menor período.
Conte as agendas diferentes, módulo .
Input
A primeira linha contém e . Cada uma das próximas linhas contém uma sequência de caracteres 0 ou 1, sem espaços. O caractere de índice da linha de índice representa .
Output
Um inteiro: a quantidade de classes de equivalência de agendas válidas, módulo .
Samples
Sample 1
Input
4 2 01 10
Output
1
As únicas agendas válidas com uma posição inicial marcada são 0101 e 1010. Elas são equivalentes.
Sample 2
Input
3 2 01 10
Output
0
Não é possível alternar as atividades e fechar um ciclo de comprimento ímpar.
Sample 3
Input
1 2 10 01
Output
2
Mesmo com um único dia, a transição da atividade para ela mesma precisa ser permitida.