AT_kupc2017_j Paint Red and Make Graph

给你一个 $H$ 行 $W$ 列的棋盘。每个格子最初被染成白色或者黑色，若 $a_{i,j}$ 是 `.`，则表示第 $i$ 行第 $j$ 列的格子是白色；若 $a_{i,j}$ 是 `#`，则该格子是黑色。你的任务是将一些白色格子涂成红色，并满足以下条件： - 每一行和每一列至少要有一个红色格子。 - 构建一个图，使其满足： - 为每个红色格子创建一个顶点（因此，顶点数与红色格子数相等）。 - 在同一行或同一列上的红色格子对应的顶点之间连一条边。 - 整个图要保持连通。 请找到白色格子涂成红色的最少数量，并计算出这种情况下的所有方案数，答案对 $10^9 + 7$ 取模。如果没有符合条件的方案，输出 `-1`。

输入是标准输入，格式如下： > $H$ $W$ > $a_{1,1}$ $\ldots$ $a_{1,W}$ > ... > $a_{H,1}$ $\ldots$ $a_{H,W}$

输出一行，包括两个整数：第一个是最小化后需要涂成红色的格子数，第二个是所有满足条件的方案数对 $10^9 + 7$ 取模的结果。如果无解，输出 `-1`。

- $1 \leq H \leq 10^4$ - $1 \leq W \leq 50$ - $H$ 和 $W$ 均为整数。 - $a_{i,j}$ 为 `.` 或 `#`。 **本翻译由 AI 自动生成**