← 返回题目列表

AtCoder · hhkb2020_e

E. 灯

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

分数: 500 点

问题陈述

我们有一个网格 H 水平行和 W 垂直的方格列,每个方格要么整齐,要么不整齐。

现在,您将在此网格中的零个或多个整齐的方块上放置灯。

灯将照亮四个方向(上、下、左、右)中的每一个方向,直到第一次到达网格边缘或不整洁的方块之前(不整洁的方块不会被照亮)。灯也会照亮它所在的方块。

给定的是整数 H, W,和 H 字符串 S_i 长度 W 每个。 如果 j- 第一个字符 S_i is .,位于 i从顶部开始的第行和 j左起第 列整齐;如果 j- 第一个字符 S_i is #,位于 i从顶部开始的第行和 j左起第列不整洁。

让 K 是整齐方块的数量。 2^K 总共放置灯的方式。 假设对于每一个 2^K 方式,计算被一盏或多盏灯照亮的方块的数量。求这些数字的模之和 1,000,000,007.

约束

  • 1 \leq H \leq 2000
  • 1 \leq W \leq 2000
  • S_i 是一个长度为 W 组成 . 和 #.

输入

输入由标准输入按以下格式给出:

H W
S_1
:
S_H

输出

打印总和,模数 1,000,000,007,被一盏或多盏灯照亮的方块数量 2^K 放置灯的方法。


示例输入 1

1 5
..#..

示例输出 1

48

有 16 总共放置灯的方式。

  • In 9 的方式(其中至少一种 1-st 和 2- 左边的第 2 个方块包含一盏灯和至少一个 4-th 和 5左边第一个方块包含一盏灯), 4 方块将被点亮。
  • In 3 的方式(其中至少一种 1-st 和 2- 左边的第 2 个方块包含一盏灯,但没有一个 4-th 和 5左边第一个方块包含一盏灯), 2 方块将被点亮。
  • 在另一个 3 的方式(其中没有一个 1-st 和 2- 左边的第 2 个方块包含一盏灯,但至少有一个 4-th 和 5左边第一个方块包含一盏灯), 2 方块将被点亮。
  • In 1 的方式(没有方格包含灯), 0 方块将被点亮。

有问题的总和是 4 \times 9 + 2 \times 3 + 2 \times 3 + 0 \times 1 = 48.


示例输入 2

2 3
..#
#..

示例输出 2

52