← 返回题目列表

AtCoder · kupc2017_j

J. 涂成红色并制作图表

中文机器翻译题面 查看原题

分数: 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