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 翻译