DMPG '17 S3 - Black and White III

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Ruby is playing with the board from a board game.

The board has 2^N \times 2^N 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 2^{N-1} \times 2^{N-1}. 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.

An example of a move.

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 2^K \times 2^K, and she knows she's performed M 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 \bmod 10^9+7.


Subtask 1 [10%]


1 \le M \le 10

Subtask 2 [20%]

1 \le K \le 4

1 \le M \le 10

Subtask 3 [30%]

1 \le K \le 4

1 \le M \le 100\,000

Subtask 4 [40%]

1 \le K \le 12

1 \le M \le 10\,000\,000

Input Specification

The first line of input will contain the space-separated integers K and M.
The next 2^K lines will each contain 2^K space-separated characters, with . representing a white tile, and # representing a black tile.

Output Specification

A single integer, the number of unique boards that could have resulted in Ruby's final folded board.

Sample Input

1 1
# .
. #

Sample Output



There are 225 possible 4 \times 4 boards that can result in the given 2 \times 2 board after one move. A few of them are shown below, but there are many more!


There are no comments at the moment.