Another Game of Life

All submissions for this problem are available.
In 1970, John Conway created a cellular automaton, the Game of Life. In this problem we will consider a modified version of the Game of Life called VastoLorde's Game of Life, and we will be focusing on just one single second of change. Suppose you start with grid $A$ which has dimensions $H \times W$. The top left cell being $A[1][1]$ and the bottom right cell being $A[H][W]$. Each cell $(i,j)$ of this grid is either "dead" or "alive". An alive cell is represented by 1 and a dead cell by 0. When Vasto clicks his fingers, this grid changes into a different grid, $B$. $B$'s dimensions are $(H1) \times (W1)$. The state of the $(i,j)$th cell of $B$ is determined by the following rule: Consider cells $A[i][j]$, $A[i+1][j]$, $A[i][j+1]$ and $A[i+1][j+1]$ i.e. the 2x2 block with $(i,j)$ at the top left corner. If exactly one diagonal of this 2x2 block is alive and the other two cells are dead, then the cell $B[i][j]$ will be alive. Otherwise, $B[i][j]$ will be dead. Formally, if either ($A[i][j] = 1, A[i+1][j+1] = 1, A[i+1][j] = 0, A[i][j+1] = 0$), or ($A[i][j] = 0, A[i+1][j+1] = 0, A[i+1][j] = 1, A[i][j+1] = 1$), then $B[i][j] = 1$. If neither of these two configurations are present, then $B[i][j] =0$. For example, suppose $H=3$, $W=3$, and grid $A$ is ``` 101 011 101 ``` This would change into the the following 2 x 2 $B$ grid: ``` 10 10 ``` Your task is, given grid $B$, determine the number of possible grids $A$ that will generate this grid when Vasto clicks his finger. Print your answer modulo $10^9 + 7$ ###Input:  The first line of input contains a single integer, $T$, the number of testcases.  The first line of each testcase contains two integers $W$ and $H$, the width and height of $B$. $H$ lines follow.  The $i$th line of each testcase contains $W$ space separated integers $B[i][1], B[i][2], \dots, B[i][W]$ such that the cell $B[i][j]$ of the grid is alive if $B[i][j]= 1$ and dead if $B[i][j] = 0$ ###Output: Print a single integer in a new line for each testcase, the number of grids $A$ that create the given grid $B$ modulo $10^9 + 7$ ###Constraints  $1 \le T \le 10$  $2 \le W \le 500$  $2 \le H \le 10$  $ B[i][j] \in \{0,1\}$ ###Sample Input: ``` 1 2 2 1 1 1 1 ``` ###Sample Output: ``` 2 ``` ###Explanation: There are two 3x3 grids that $A$ could be, so that it changes into the 2x2 grid in the input. They are ``` 101 010 101 ``` and ``` 010 101 010 ```Author:  vastolorde95 
Tags  vastolorde95 
Date Added:  14122018 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 