分数: 400 点
问题陈述
有一个网格 H 行和 W 列。
最初,网格中的每个单元格都被漆成白色或黑色。 i第行和 j- 第列被漆成白色,如果 a_{i,j} is .。如果它被漆成黑色 a_{i,j} is #。
您希望在以下限制范围内将一些白色单元格涂成红色。
- 每行和每列必须有一个或多个红色单元格。
- 当按如下方式构造图时,该图必须是连通的。
- 对于所有红色单元格,创建相应的顶点。 (图中的顶点数等于网格中红色单元格的数量。)
- 向所有对应单元格位于同一行或同一列的顶点对添加边。
找到满足上述约束条件需要涂成红色的最小单元格数。 另外,找到这种方式的数量(红细胞数量最少的地方)模块 10^9 + 7.
约束
- 1 \leq H \leq 10^4
- 1 \leq W \leq 50
- H, W 是整数。
- a_{i,j} 是
.or#.
输入
输入由标准输入按以下格式给出:
H W
a_{1,1} ... a_{1,W}
:
a_{H,1} ... a_{H,W}
输出
打印出需要涂成红色的最小单元格数量以及这种方式的数量,中间有一个空格。
如果没有办法满足约束,则仅打印 -1 代替。
示例输入 1
2 3 ... .#.
示例输出 1
4 4
有 4 绘制网格的方法。o 代表红细胞。 )
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