English · Original
Chinese · Translation
Formal · Original
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.
## Input
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_.
## Output
Output the number of suitable plans modulo 109 + 7.
[samples]
## Note
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.
Polycarp 在 Berland 的首都拥有一家商店。最近首都的犯罪活动增加了，因此 Polycarp 正在考虑为其商店的仓库建立更好的安保措施。
仓库可以表示为一个包含 #cf_span[n] 行和 #cf_span[m] 列的矩阵。矩阵的每个元素要么是 _._（空格），要么是 _x_（墙）。
Polycarp 希望雇佣一些守卫（可能为零）来监视仓库。每个守卫将位于矩阵的某个单元格中，并保护其右侧的所有单元格和其下方的所有单元格，直到遇到最近的墙。更正式地，如果守卫位于单元格 #cf_span[(x0, y0)]，则他保护单元格 #cf_span[(x1, y1)] 当且仅当满足以下所有条件：
守卫只能放置在空格中（且只能保护空格）。守卫的放置方案是守卫将被放置的一组单元格（当然，如果存在至少一个单元格仅出现在第一个方案中而不出现在第二个方案中，或反之，则这两个方案不同）。Polycarp 称一个方案为 _合适的_，如果未被保护的空格数量 _不超过一个_。
Polycarp 想要知道合适的方案数量。由于数量可能很大，你必须输出其对 #cf_span[109 + 7] 取模的结果。
第一行包含两个数 #cf_span[n] 和 #cf_span[m] —— 仓库的长和宽（#cf_span[1 ≤ n, m ≤ 250]，#cf_span[1 ≤ nm ≤ 250]）。
接下来 #cf_span[n] 行，第 #cf_span[i] 行包含一个由 #cf_span[m] 个字符组成的字符串 —— 表示仓库的第 #cf_span[i] 行矩阵。每个字符要么是 _._，要么是 _x_。
请输出合适的方案数量对 #cf_span[109 + 7] 取模的结果。
在第一个例子中，你必须放置至少一个守卫，因此有三种可能的安排：一个守卫在单元格 #cf_span[(1, 1)]，一个守卫在单元格 #cf_span[(1, 3)]，以及两个守卫分别在这两个单元格中。
## Input
第一行包含两个数 #cf_span[n] 和 #cf_span[m] —— 仓库的长和宽（#cf_span[1 ≤ n, m ≤ 250]，#cf_span[1 ≤ nm ≤ 250]）。接下来 #cf_span[n] 行，第 #cf_span[i] 行包含一个由 #cf_span[m] 个字符组成的字符串 —— 表示仓库的第 #cf_span[i] 行矩阵。每个字符要么是 _._，要么是 _x_。
## Output
请输出合适的方案数量对 #cf_span[109 + 7] 取模的结果。
[samples]
## Note
在第一个例子中，你必须放置至少一个守卫，因此有三种可能的安排：一个守卫在单元格 #cf_span[(1, 1)]，一个守卫在单元格 #cf_span[(1, 3)]，以及两个守卫分别在这两个单元格中。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the storehouse matrix.
Let $ G \in \{0,1\}^{n \times m} $ be the grid, where $ G[i][j] = 1 $ if cell $ (i,j) $ is an empty space (`.`), and $ G[i][j] = 0 $ if it is a wall (`x`).
Let $ E = \{ (i,j) \in [n] \times [m] \mid G[i][j] = 1 \} $ be the set of empty cells.
For a guard placed at $ (x_0, y_0) \in E $, define its **protection region**:
$$
P(x_0, y_0) = \left\{ (x_1, y_1) \in E \mid x_1 \ge x_0,\ y_1 \ge y_0,\ \nexists (x', y') \in E^c \text{ with } x_0 \le x' \le x_1,\ y_0 \le y' \le y_1 \right\}
$$
(i.e., the set of empty cells weakly southeast of $ (x_0, y_0) $, bounded by walls).
A **plan** is a subset $ S \subseteq E $.
A plan $ S $ is **suitable** if the number of empty cells **not** protected by any guard in $ S $ is at most 1:
$$
\left| E \setminus \bigcup_{(x_0,y_0) \in S} P(x_0, y_0) \right| \le 1
$$
**Constraints**
1. $ 1 \le n, m \le 250 $, $ n \cdot m \le 250 $
2. $ G[i][j] \in \{0,1\} $ for all $ i \in [n], j \in [m] $
3. $ |E| \le 250 $
**Objective**
Compute the number of suitable plans $ S \subseteq E $, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "F. Guards In The Storehouse",
"description": {
"content": "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. ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF845F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Polycarp 在 Berland 的首都拥有一家商店。最近首都的犯罪活动增加了，因此 Polycarp 正在考虑为其商店的仓库建立更好的安保措施。\n\n仓库可以表示为一个包含 #cf_span[n] 行和 #cf_span[m] 列的矩阵。矩阵的每个元素要么是 _._（空格），要么是 _x_（墙）。\n\nPolycarp 希望雇佣一些守卫（可能为零）来监视仓库。每个守卫将位于矩阵的某个单元格中，并...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the storehouse matrix. \nLet $ G \\in \\{0,1\\}^{n \\times m} $ be the grid, where $ G[i][j] = 1 $ if cell $ (i,j) $ is an empty space ...",
"is_translate": false,
"language": "Formal"
}
]
}