AT_kupc2017_j Paint Red and Make Graph

[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_j $ H $ 行 $ W $ 列の盤面が目の前にあります。 各マスは最初は白か黒のいずれかの色で塗られており、$ a_{i,j} $ が `.` のときは $ i $ 行 $ j $ 列目のマスは白に、`#` のときは黒に塗られています。 あなたは、以下の条件を満たすように白のマスの一部を赤に塗り替えたいと考えています。 - 全ての列と行には少なくともひとつの赤マスがある。 - 以下のようにグラフを構成したとき、そのグラフは連結である。 - 全ての赤マスに対して、対応する頂点を作る。 (このとき、グラフの頂点数と赤マスの数は等しい。) - 同じ行または同じ列にあるマスに対応する頂点同士に辺を張る。 以上の条件を満たすように赤マスに塗り替えるとき、赤マスに塗り替える白マスの数の最小値を求めてください。 また、赤マスに塗り替える白マスの数が最小となるような塗り方の個数を $ 10^9\ +\ 7 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ a_{1,1} $ $ ... $ $ a_{1,W} $ $ : $ $ a_{H,1} $ $ ... $ $ a_{H,W} $

赤マスに塗り替える白マスの数の最小値とそのときの塗り方の個数を $ 10^9\ +\ 7 $ で割った余りを空白区切りで一行に出力せよ。 条件を満たす塗り方が存在しない場合は `-1` のみを出力せよ。

### 制約 - $ 1\ \leq\ H\ \leq\ 10^4 $ - $ 1\ \leq\ W\ \leq\ 50 $ - $ H $, $ W $ は整数である。 - $ a_{i,j} $ は `.` か `#` のいずれかである。 ### Sample Explanation 1 赤マスに塗られたマスを `o` で表したとき、塗り方は以下の $ 4 $ 通りです。 ``` ooo ooo oo. .oo o#. .#o o#o o#o ``` ### Sample Explanation 2 条件を満たす塗り方は存在しません。