Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito tiene un tablero de N filas y M columnas que tiene algunas de sus casillas marcadas. Él siempre lo utiliza para jugar su juego de mesa favorito, pero hoy desea algo diferente. Fito quiere saber de cuántas formas es posible poner piezas en su tablero tal que a lo sumo haya un pieza por casilla marcada (y ninguna en las casillas no marcadas), y no haya dos casillas adyacentes ambas con piezas (dos casillas son adyacentes si comparten un lado), ayúdalo a resolver su problema.

La primera línea contiene dos enteros N y M que representan la cantidad de filas y columnas del tablero respectivamente.
Las próximas N líneas contienen cada una M enteros separados por espacio, esta será la descripción del tablero, cada línea representa una fila. Si el entero en la fila A y la columna B es un uno, entonces la posición del tablero correspondiente se considera marcada.
-para el primer subproblema  1 ≤ N ≤ 12 y 1 ≤ M ≤ 12.
-para el segundo subproblema 1 ≤ N ≤ 1100100100 y 1 ≤ M ≤ 2, y además, en el segundo subproblema no habrá descripcion del tablero y se puede considerar que todas las casillas están marcadas.