Grid Coloring with Parity Constraints

Sam and his sister Sara have a grid of \(n \times m\) cells. They want to color each cell either red or blue such that every \(2 \times 2\) subgrid contains an odd number (either \(1\) or \(3\)) of red cells. Some cells have already been colored and are represented as follows: 'R' for red, 'B' for blue, and '?' for cells that still need to be colored.

If we represent red as \(1\) and blue as \(0\), then for any \(2 \times 2\) block with cells \(a, b, c, d\) (in row-major order), the condition can be written as:

[ a + b + c + d \equiv 1 \pmod{2}. ]

Your task is to determine whether it is possible to fill in the missing colors so that the entire grid satisfies the condition, and if so, count the number of valid colorings modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n, m \le 500)\) — the number of rows and columns.

The next \(n\) lines each contain a string of length \(m\). Each character is either 'R' (red), 'B' (blue), or '?' (unknown), indicating the pre-colored cells and the cells that need to be colored.

outputFormat

Output a single integer — the number of valid colorings of the grid such that every \(2 \times 2\) subgrid contains an odd number of red cells, modulo \(10^9+7\).

sample

3 5
BBRBR
RBBBB
RRBRB

1