← 返回题目列表

Codeforces · 845/F

F. 仓库里的守卫

中文机器翻译题面 查看原题

波利卡普在伯兰首都拥有一家商店。最近首都的犯罪活动有所增加,因此波利卡普正在考虑在他的商店的仓库中建立一些更好的安全措施。

仓库可以表示为一个 n 行 m 列的矩阵。矩阵的每个元素都是 . (空的空间)或 x(墙)。

坡旅甲想要雇佣一些警卫(可能是零)来看守仓库。每个守卫将位于矩阵的某个单元格中,并保护自己单元格右侧的每个单元格和自己单元格底部的每个单元格,直到最近的墙壁。更正式地说,如果警卫站在牢房 (x0, y0) 中,那么如果满足所有这些条件,他就会保护牢房 (x1, y1):

- (x1, y1) 是一个空单元格;
- x0 = x1 且 y0 ≤ y1,或 x0 ≤ x1 且 y0 = y1;
- 单元 (x0, y0) 和 (x1, y1) 之间没有墙。这些牢房之间可以有警卫,警卫可以互相看穿。

守卫只能放置在空单元格中(并且只能保护空单元格)。放置守卫的计划是放置守卫的一些单元格(当然,如果存在至少一个单元格包含在第一个计划中,但不包含在第二个计划中,则两个计划是不同的,反之亦然)。如果不存在超过一个不受保护的空单元,波利卡普就认为该计划是合适的。

Polycarp 想知道合适计划的数量。由于它可能非常大,因此必须以 109 + 7 为模输出。

输入

第一行包含两个数字n和m——仓库的长度和宽度(1≤n,m≤250,1≤nm≤250)。

接下来是n行,第i行包含一个由m个字符组成的字符串——矩阵的第i行代表仓库。每个字符都是 .或 x。

输出

输出以 109 + 7 为模的合适计划的数量。

示例

输入 #1

1 3
.x.

输出 #1

3

输入 #2

2 2
xx
xx

输出 #2

1

输入 #3

2 2
..
..

输出 #3

10

输入#4

3 1
x
.
x

输出#4

2

注意

在第一个示例中,您必须至少放置一名警卫,因此存在三种可能的安排:牢房 (1, 1) 中一名警卫,牢房 (1, 3) 中一名警卫,以及这两个牢房中两名警卫。