Ruby is playing with the board from a board game.
The board has cells, originally coloured some assortment of black and white. Ruby takes this board and folds it a number of times, once on the middle vertical axis followed by once on the middle horizontal axis, resulting in a board of size . When she folds on the vertical, she always keeps the left side stationary, and folds the right half onto it. She does the same for horizontal folds, holding the top half stationary.
Whenever a black tile is folded onto a white tile, the resulting tile is a black tile. Ruby defines a move as a vertical fold followed by a horizontal fold.
Ruby has performed a number of moves on her board, but in doing so forgot what her original board looked like! Her board is currently size , and she knows she's performed moves so far.
In this game, orientation of the board does matter. That is, the board is not the same as .
Given her folded board, how many distinct assortments of tiles in the original board could have resulted in her current board? Since this number may be quite large, output it .
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [40%]
The first line of input will contain the space-separated integers and .
The next lines will each contain space-separated characters, with
. representing a white tile, and
# representing a black tile.
A single integer, the number of unique boards that could have resulted in Ruby's final folded board.
1 1 # . . #
There are 225 possible boards that can result in the given board after one move. A few of them are shown below, but there are many more!