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 自动生成