/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
H 行 W 列の盤面が目の前にあります。
各マスは最初は白か黒のいずれかの色で塗られており、a_{i,j} が . のときは i 行 j 列目のマスは白に、# のときは黒に塗られています。
あなたは、以下の条件を満たすように白のマスの一部を赤に塗り替えたいと考えています。
- 全ての列と行には少なくともひとつの赤マスがある。
- 以下のようにグラフを構成したとき、そのグラフは連結である。
- 全ての赤マスに対して、対応する頂点を作る。 (このとき、グラフの頂点数と赤マスの数は等しい。)
- 同じ行または同じ列にあるマスに対応する頂点同士に辺を張る。
以上の条件を満たすように赤マスに塗り替えるとき、赤マスに塗り替える白マスの数の最小値を求めてください。 また、赤マスに塗り替える白マスの数が最小となるような塗り方の個数を 10^9 + 7 で割った余りを求めてください。
制約
- 1 \leq H \leq 10^4
- 1 \leq W \leq 50
- H, W は整数である。
- a_{i,j} は
.か#のいずれかである。
入力
入力は以下の形式で標準入力から与えられる。
H W
a_{1,1} ... a_{1,W}
:
a_{H,1} ... a_{H,W}
出力
赤マスに塗り替える白マスの数の最小値とそのときの塗り方の個数を 10^9 + 7 で割った余りを空白区切りで一行に出力せよ。
条件を満たす塗り方が存在しない場合は -1 のみを出力せよ。
入力例1
2 3 ... .#.
出力例1
4 4
赤マスに塗られたマスを o で表したとき、塗り方は以下の 4 通りです。
ooo ooo oo. .oo o#. .#o o#o o#o
入力例2
2 3 #.. .##
出力例2
-1
条件を満たす塗り方は存在しません。
入力例3
3 10 ...#...#.. #...#...#. ..##......
出力例3
12 35640
入力例4
6 6 ...... ...... ...... ...... ...... ......
出力例4
11 60466176
Score : 400 points
Problem Statement
There is a grid with H rows and W columns.
Originally, each cell in the grid is painted white or black. The cell on the i-th row and j-th column is painted white if a_{i,j} is .. It is painted black if a_{i,j} is #.
You want to paint some white cells red within the following constraints.
- Each row and column must have one or more red cells.
- When a graph is constructed as follows, the graph must be connected.
- For all red cells, create the corresponding vertices. (The number of vertices in the graph is equal to the number of red cells in the grid. )
- Add edges to all pairs of vertices, the corresponding cells of which are on the same row or column.
Find the minimum number of cells you need to paint red to sarisfy the above constraints. Also, find the number of such ways (where the number of red cells is minimum) module 10^9 + 7.
Constraints
- 1 \leq H \leq 10^4
- 1 \leq W \leq 50
- H, W are integers.
- a_{i,j} is either
.or#.
Input
Input is given from Standard Input in the following format:
H W
a_{1,1} ... a_{1,W}
:
a_{H,1} ... a_{H,W}
Output
Print the minimum number of cells you need to paint red and the number of such ways, with a single space in between.
If there's no ways to satisfy the constraints, print only -1 instead.
Sample Input 1
2 3 ... .#.
Sample Output 1
4 4
There are 4 ways to paint the grid. (o represents a red cell. )
ooo ooo oo. .oo o#. .#o o#o o#o
Sample Input 2
2 3 #.. .##
Sample Output 2
-1
There are no ways to satisfy the constraints.
Sample Input 3
3 10 ...#...#.. #...#...#. ..##......
Sample Output 3
12 35640
Sample Input 4
6 6 ...... ...... ...... ...... ...... ......
Sample Output 4
11 60466176