DrawingBlackCrosses

Pavel likes puzzles. One of his favorite puzzles is DrawingBlackCrosses. In this puzzle, the player starts with a rectangular grid of cells, where each cell is either white or black, and at most 8 of the cells are black. The player's goal is to achieve the state where all of the cells in the grid are black. To achieve this goal, a sequence of moves must be performed. In each move, a single white cell is selected and all white cells located in the same row and all white cells located in the same column as the selected cell, including the selected cell itself, are colored black. The moves are performed until there are no more white cells.

Each solution to this puzzle can be written as a sequence of cells, where the i-th cell in the sequence is the cell that was selected on the player's i-th move. Two solutions are considered to be different if these sequences have different lengths or if there's an index i such that the i-th cells in these sequences are different. You are given a String[] field representing the initial state of the grid. The j-th character in the i-th element of field is '.' if the cell in row i, column j of the grid is initially white and 'B' if this cell is initially black. Return the number of different solutions that exist for the given grid, modulo 1000000007.