D - Juego con tablero I

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, JavaScript, ... (details)

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.

Input

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.

Output

Una única línea con la cantidad de formas de dejar el tablero, como este número puede ser muy grande, imprima en su lugar el resto que deja al ser dividido por 10^8.
En el caso del segundo subproblema, como este número puede ser muy grande, imprima en su lugar el resto que deja al ser dividido por 10^9+9

Sample test(s)

Input
2 3 1 1 1 0 1 0
Output
9