D. Pinturas sobrepostas
Um painel é formado por todos os quadradinhos unitários do plano com vértices em coordenadas inteiras. Inicialmente, todos estão brancos.
Há carimbos retangulares disponíveis. O carimbo tem cantos opostos e . Usá-lo troca a cor de cada quadradinho dentro desse retângulo: branco vira preto e preto vira branco.
Você pode escolher qualquer subconjunto dos carimbos e usar cada carimbo escolhido exatamente uma vez. A ordem de uso não importa. Quantas pinturas finais diferentes podem ser obtidas? Duas pinturas são diferentes se algum quadradinho tem cores diferentes. Subconjuntos diferentes que produzem a mesma pintura contam apenas uma vez. Inclua a pintura inteiramente branca.
Input
A primeira linha contém (). Cada uma das próximas linhas contém ( e ). Carimbos com o mesmo retângulo são permitidos.
Output
Imprima o número de pinturas distintas módulo .
Samples
Sample 1
Input
3 0 0 1 1 1 0 2 1 0 0 2 1
Output
4
Usar os dois primeiros carimbos tem o mesmo efeito de usar apenas o terceiro. As pinturas possíveis são: nenhuma região preta, apenas o quadradinho da esquerda, apenas o da direita ou ambos.
Sample 2
Input
2 0 0 3 3 0 0 3 3
Output
2
Usar ambos os carimbos apaga o que o primeiro pintou. Só existem duas pinturas.
Sample 3
Input
2 0 0 2 2 1 1 3 3
Output
4
Nenhum carimbo, só o primeiro, só o segundo e ambos produzem quatro pinturas diferentes.