Problem Description

You have a board with $ H $ rows and $ W $ columns. Each cell is initially painted either white or black, where $ a_{i,j} $ is . if the cell at the $ i $-th row and $ j $-th column is white, and # if it is black. You want to repaint some of the white cells to red such that the following conditions are satisfied:

• Every row and column contains at least one red cell.
• When constructing a graph as follows, the graph is connected:
• Create a vertex for each red cell. (The number of vertices in the graph is equal to the number of red cells.)
• Connect vertices with an edge if they correspond to cells in the same row or the same column.

Find the minimum number of white cells that need to be repainted to red to satisfy the above conditions. Also, find the number of ways to repaint the cells to achieve this minimum number, modulo $ 10^9 + 7 $.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ a_{1,1} $ $ ... $ $ a_{1,W} $ $ : $ $ a_{H,1} $ $ ... $ $ a_{H,W} $

Output Format

Output the minimum number of white cells to be repainted to red and the number of ways to achieve this, modulo $ 10^9 + 7 $, separated by a space. If there is no way to satisfy the conditions, output -1.

Sample Input and Output

Sample Input #1

2 3
...
.#.

Sample Output #1

4 4

Sample Input #2

2 3
#..
.##

Sample Output #2

-1

Sample Input #3

3 10
...#...#..
#...#...#.
..##......

Sample Output #3

12 35640

Sample Input #4

6 6
......
......
......
......
......
......

Sample Output #4

11 60466176

Notes/Hints

Constraints

• $1 \leq H \leq 10^4$
• $1 \leq W \leq 50$
• $ H $ and $ W $ are integers.
• $ a_{i,j} $ is either . or #.

Sample Explanation 1

When the red cells are represented by o, there are $ 4 $ ways to repaint the cells as follows:

ooo ooo oo. .oo
o#. .#o o#o o#o

Sample Explanation 2

There is no way to satisfy the conditions.

见题面 Input 部分

见题面 Output 部分