Binarizing the Matrix
By Gabriel Duarte, UFF 
Brazil
By Gabriel Duarte, UFF Brazil
Dabriel is playing around with his beautiful binary matrix, where he can put 0 or 1 in each position of it. As we already know, Dabriel loves to create rules and games, so he proposed the following:
- For every cell with a value of 1, the whole submatrix that goes from the leftmost corner to it must also have a value of 1;
- Every cell in the matrix has to receive a binary value;
- Cells that already have some value can not be changed.
With that in mind, Dabriel wants to know how many different ways there are to accomplish the game. Can you figure it out?
The first line of the test case contains two integers N and M (1 ≤ N, M ≤ 100), representing the number of rows and columns of the matrix, respectively. The next N lines contain M characters, being: '.', '1', '0', where '.' represents a cell that has not yet received a binary value.
Print out the amount of possible possibilities for Dabriel's game. Since this amount can be very large, print only the rest of the division of that quantity by 109+7.
| Exemplo de Entrada | Exemplo de Saída |
|
3 2 |
6 |