CF845F.Guards In The Storehouse

Polycarp owns a shop in the capital of Berland. Recently the criminal activity in the capital increased, so Polycarp is thinking about establishing some better security in the storehouse of his shop.

The storehouse can be represented as a matrix with n rows and m columns. Each element of the matrix is either . (an empty space) or x (a wall).

Polycarp wants to hire some guards (possibly zero) to watch for the storehouse. Each guard will be in some cell of matrix and will protect every cell to the right of his own cell and every cell to the bottom of his own cell, until the nearest wall. More formally, if the guard is standing in the cell (_x_0, _y_0), then he protects cell (_x_1, _y_1) if all these conditions are met:

• (_x_1, _y_1) is an empty cell;
• either _x_0 = _x_1 and _y_0 ≤ _y_1, or _x_0 ≤ _x_1 and _y_0 = _y_1;
• there are no walls between cells (_x_0, _y_0) and (_x_1, _y_1). There can be a guard between these cells, guards can look through each other.

Guards can be placed only in empty cells (and can protect only empty cells). The plan of placing the guards is some set of cells where guards will be placed (of course, two plans are different if there exists at least one cell that is included in the first plan, but not included in the second plan, or vice versa). Polycarp calls a plan suitable if there is not more than one empty cell that is not protected.

Polycarp wants to know the number of suitable plans. Since it can be very large, you have to output it modulo 109 + 7.

Polycarp 在 Berland 首都拥有一家商店。最近首都的犯罪活动加剧，因此 Polycarp 正在考虑为其商店仓库加强安保措施。

仓库可表示为一个 $n$ 行 $m$ 列的矩阵。矩阵中每个元素要么是 .（空地），要么是 x（墙壁）。

Polycarp 打算雇佣若干名守卫（可以为零名）来监视仓库。每名守卫将位于矩阵中的某个格子，并保护其所在格子右侧所有格子以及其所在格子下方所有格子，直至遇到最近的墙壁为止。更准确地说，若一名守卫位于格子 $(x_0, y_0)$，则他能保护格子 $(x_1, y_1)$ 当且仅当满足以下全部条件：

• $(x_1, y_1)$ 是一个空地；
• 要么 $x_0 = x_1$ 且 $y_0 \le y_1$，要么 $x_0 \le x_1$ 且 $y_0 = y_1$；
• 格子 $(x_0, y_0)$ 与 $(x_1, y_1)$ 之间不存在墙壁。这两格之间可以有其他守卫——守卫彼此互不遮挡视线。

守卫只能放置在空地上（且仅能保护空地）。一种守卫布置方案即为一组选定的、将要放置守卫的格子集合（显然，若存在至少一个格子属于第一个方案但不属于第二个方案，或反之，则这两个方案不同）。Polycarp 称一个方案是合适的，当且仅当未被保护的空地格子至多只有一个。

Polycarp 想知道合适方案的总数。由于该数可能非常大，请你输出其对 $10^9 + 7$ 取模的结果。

The first line contains two numbers n and m — the length and the width of the storehouse (1 ≤ n, m ≤ 250, 1 ≤ nm ≤ 250).

Then n lines follow, _i_th line contains a string consisting of m characters — _i_th row of the matrix representing the storehouse. Each character is either . or x.

第一行包含两个数字 $n$ 和 $m$ —— 分别表示仓库的长度和宽度（$1 \leq n, m \leq 250$，且 $1 \leq nm \leq 250$）。

接下来是 $n$ 行，第 $i$ 行包含一个由 $m$ 个字符组成的字符串 —— 表示代表仓库的矩阵的第 $i$ 行。每个字符要么是 .，要么是 x。

Output the number of suitable plans modulo 109 + 7.

输出合适方案的数量对 $10^9 + 7$ 取模的结果。

In the first example you have to put at least one guard, so there are three possible arrangements: one guard in the cell (1, 1), one guard in the cell (1, 3), and two guards in both these cells.

在第一个例子中，你至少需要放置一名守卫，因此共有三种可能的布置方式：一名守卫放在单元格 $(1, 1)$ 中，一名守卫放在单元格 $(1, 3)$ 中，或两名守卫分别放在这两个单元格中。