AT_hhkb2020_e.Lamps

有一个由 $H$ 行 $W$ 列组成的网格，每个格子要么是“散乱的”，要么是“未散乱的”。

现在你可以在 $0$ 个或更多未散乱的格子上放置照明灯。

每个照明灯会照亮其所在格子，以及从该格子向上下左右四个方向，直到遇到网格边界或第一个“散乱的”格子为止（“散乱的”格子不会被照亮）。照明灯所在的格子也会被照亮。

给定整数 $H,\ W$ 和 $H$ 个长度为 $W$ 的字符串 $S_i$。当 $S_i$ 的第 $j$ 个字符为 . 时，第 $i$ 行第 $j$ 列的格子是未散乱的；当 $S_i$ 的第 $j$ 个字符为 # 时，第 $i$ 行第 $j$ 列的格子是散乱的。

假设未散乱的格子的总数为 $K$，则照明灯的放置方法共有 $2^K$ 种。对于这 $2^K$ 种放置方法中的每一种，计算被至少一个照明灯照亮的格子的数量，并将所有方案的总和对 $1,000,000,007$ 取模后输出。

输入按以下格式从标准输入给出。

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

对于所有 $2^K$ 种放置方法，计算每种情况下被至少一个照明灯照亮的格子的数量之和，并输出其对 $1,000,000,007$ 取模的结果。

限制条件

• $1 \leq H \leq 2000$
• $1 \leq W \leq 2000$
• $S_i$ 是仅由 . 和 # 组成的长度为 $W$ 的字符串

样例解释 1

一共有 $16$ 种放置照明灯的方法。

• 其中 $9$ 种（左起第 $1$ 或第 $2$ 个至少有一个放了灯，且左起第 $4$ 或第 $5$ 个至少有一个放了灯）会照亮 $4$ 个格子。
• 其中 $3$ 种（左起第 $1$ 或第 $2$ 个至少有一个放了灯，且左起第 $4$ 和第 $5$ 个都没有放灯）会照亮 $2$ 个格子。
• 其中 $3$ 种（左起第 $4$ 或第 $5$ 个至少有一个放了灯，且左起第 $1$ 和第 $2$ 个都没有放灯）会照亮 $2$ 个格子。
• 其中 $1$ 种（一个灯也没放）会照亮 $0$ 个格子。
  所以答案为 $4 \times 9 + 2 \times 3 + 2 \times 3 + 0 \times 1 = 48$。

由 ChatGPT 4.1 翻译