Flipping
Time limit5sMemory limit256 MB
Count initial black/white colorings of an N by M grid that can reach the given coloring when a press inverts the whole monochromatic connected component containing that cell, modulo 1e9+7.
- Level
Hard9 of 10
- Topics
- Graph, Union-find, Math, Combinatorics
- Solved
- No attempts yet
Problem
One day, while walking down the street, Neo picked up a grid board. The board has N rows and M columns, and each cell is painted either white or black.
Neo thought that this board surely hid a tremendous secret, so he decided to try decoding it later. The figure below shows an example of a board's state.
While Neo was out for a while, Frodo examined Neo's board from various angles. Before long, he observed that pressing a single cell inverts the color of every cell connected to it, including itself. Here, two cells are connected if you can travel between them using only cells of the same color that share an edge. When Neo came home, he was dismayed to learn that Frodo had changed the board's state. But since he knows the final state, he decided to hold onto the hope that he could infer the initial state.
Frodo pressed the board zero or more times (it may be that he has not pressed it yet). Given the current color of each cell, find the number of possible initial states of the board, modulo 1,000,000,007(10⁹ + 7). Two board states are defined to be different when there exists a position whose cell color differs.
Input
The first line gives the number of rows N and the number of columns M of the board. (1 ≤ N, M ≤ 2,000)
From the second line, N lines follow, each a string representing the current color of each cell.
Among the N lines, the j-th character of the i-th line represents the color of the cell at row i, column j: 'B' means black and 'W' means white.
Output
On the first line, print the number of possible initial states of the board, modulo 1,000,000,007(10⁹ + 7).