eolymp
bolt
Try our new interface for solving problems
Problems

Dominoes

Dominoes

Time limit 1 second
Memory limit 128 MiB

Dora likes to play with dominoes. She takes n * m table, marks some cells as occupied, and then tries to fill all unoccupied cells with 2 * 1 dominoes.

prb11323.gif

Her little brother Dani loves to play pranks on his older sister. So when she is away, he marks two more unoccupied cells as occupied. He wants to do it in such a way that it will be impossible to fill all unoccupied cells with dominoes.

Help Dani to count the number of ways he can select these two cells. Since Dani can only count to one million, if this number of ways is x, output min(x, 10^6).

Input data

The first line contains integers n and m (1n, m1000). Next n lines contain m characters each - the initial state of the table. Character "#" corresponds to an occupied cell, and character "." corresponds to an unoccupied cell. It is guaranteed that there are at least two unoccupied cells, and that it is possible to fill all unoccupied cells with dominoes.

Output data

Let x be the number of ways Dani can mark two cells in such a way that it will be impossible to fill all unoccupied cells with dominoes.

Print one integer min(x, 10^6).

Examples

Input example #1
3 6
...#..
......
#...##
Output example #1
52
Input example #2
2 2
..
..
Output example #2
2
Input example #3
2 2
#.
#.
Output example #3
0
Source 2022 ICPC, NERC, December 7