408881: GYM103371 I Organizing Colored Sheets

There is a large grid of size $$$n \times m$$$, where each grid cell is either colored or uncolored.

To make some artwork on the grid, Hyunuk wants to put some sheets of colored paper in some of the uncolored cells. Hyunuk selects two integers $$$w, h$$$ where $$$1 \le w \le m, 1 \le h \le n$$$. Then, Hyunuk covers the grid with sheets of colored paper of width $$$w$$$ and height $$$h$$$, satisfying the following conditions.

• The colored paper should exactly cover the grid cells, and not go out of the grid.
• The colored paper cannot be rotated.
• A cell may be covered with more than one sheet of colored paper.
• Every uncolored cell must be covered with at least one sheet of colored paper.
• No colored cell can be covered with any colored paper.

Depending on the selection of width and height, Hyunuk may fail to cover the grid satisfying the above conditions. Please compute the number of possible sheet sizes that can cover the grid satisfying all the above conditions.

The first line contains two integers $$$n$$$ and $$$m \, (1 \le n, m \le 3\,000)$$$.

The next $$$n$$$ lines each contain a length $$$m$$$ string denoting the state of the grid. . denotes an uncolored cell, and # denotes a colored cell.

There is at least one uncolored cell in the grid.

Output the number of possible sheet sizes that can cover the grid satisfying all the above conditions.

3 3
..#
...
#..

4

8 9
.........
.........
.........
...#.....
.....#...
....#....
.........
.........

4

9 9
######...
######...
######...
#........
#.....###
#.....###
#####....
#####....
#####....

9

5 5
.....
....#
...##
..###
.####

1

In the first example, the following four colored paper satisfy the conditions: $$$1 \times 1$$$, $$$1 \times 2$$$, $$$2 \times 1$$$, and $$$2 \times 2$$$. Since the colored paper can not be rotated, $$$1 \times 2$$$ and $$$2 \times 1$$$ are considered different sizes.