#215606. [ICPC 2025 APC] Control Towers

You are an architect tasked with designing the new airport in your city. After you have completed your design, you just realize you forgot to allocate spaces for the control towers.

The layout of the new airport can be represented by a 2D grid of rows and columns, with the rows numbered from to (top to bottom) and the columns numbered from to (left to right). The cell in row and column is denoted by . Each cell can either be occupied or empty.

You need to place four control towers (numbered from to ), each in a different empty cell. To allow easier communication between different towers, for all , you want tower and tower to be placed either in the same row or in the same column.

You want to calculate the number of ways to place the control towers to satisfy the requirements above. Two ways are considered different if there exists where control tower is placed in different cells.

The first line of input contains two integers and (). Each of the next lines contains a string of characters. The -th character in the -th line is if cell is occupied; otherwise, it is (dot).

Output the number of ways to place the control towers to satisfy the requirements above.

样例输入 1

3 4
.#.#
#...
.###

样例输出 1

10

样例输入 2

4 6
######
#.#.#.
.#.#.#
######

样例输出 2

0

样例输入 3

1 10
..........

样例输出 3

5040

样例输入 4

1 10
##########

样例输出 4

0

Explanation for the sample input/output #1

Figure A.1 illustrates all possible ways to place the control towers, where the cells numbered , , , and represent control towers , , , and respectively.

:::align{center}

Figure A.1: All possible ways to place the control towers. :::

Explanation for the sample input/output #2

It is impossible for any control tower in row to be in the same column as any control tower in row . Since there are not enough empty cells to place all four control towers in the same row, there is no way to place the control towers to satisfy the requirements above.

Explanation for the sample input/output #3

All ways of control tower positions satisfy the requirements above.

Explanation for the sample input/output #4

There is no empty cell to place any control tower.