题目描述

我们有一个 $H$ 行 $W$ 列的网格，每个方格都是整洁或杂乱的。

你现在要在这个网格中的一个或多个整洁方格上放置灯。

一盏灯将照亮四个方向（向上、向下、向左和向右），直到达到网格的边缘或第一次遇到杂乱方格为止（杂乱方格不会被照亮）。这盏灯还将照亮它所处的方格。

给定整数 $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$ 取模的结果。

约束条件

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

输入

输入以以下格式从标准输入中给出：

$H$ $W$

$S_1$

$:$

$S_H$

输出

打印在 $2^K$ 种放置灯的方式下由一个或多个灯照亮的方格的数量之和对 $1,000,000,007$ 取模的结果。

示例 1

1 5
..#..

示例输出 1

48

总共有 $16$ 种放置灯的方式。

• 在 $9$ 种方式中（至少左侧的第 $1$ 个和第 $2$ 个方格之一包含灯，至少左侧的第 $4$ 个和第 $5$ 个方格之一包含灯），有 $4$ 个方格被照亮。
• 在 $3$ 种方式中（左侧的第 $1$ 个和第 $2$ 个方格之一包含灯，左侧的第 $4$ 个和第 $5$ 个方格都不包含灯），有 $2$ 个方格被照亮。
• 在另外 $3$ 种方式中（左侧的第 $1$ 个和第 $2$ 个方格都不包含灯，至少左侧的第 $4$ 个和第 $5$ 个方格之一包含灯），有 $2$ 个方格被照亮。
• 在 $1$ 种方式中（没有方格包含灯），没有方格被照亮。

所求和为 $4 \times 9 + 2 \times 3 + 2 \times 3 + 0 \times 1 = 48$。

示例 2

2 3
..#
#..

示例输出 2

52