该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 5F. 守卫

时间限制：1000ms

空间限制：256MB

Description

给定一个n行m列的矩阵。矩阵的每个元素要么是.（空格），要么是x（墙壁）。zms 把一些守卫放置于矩阵的某个单元格中，并保护他自己单元格右侧和下方的每个单元格，直到最近的墙壁。

正式地说，如果守卫站在单元格 \((x_0，y_0)\) 中，如果满足以下所有条件则他保护单元格 \((x_1，y_1)\) ：

• \((x_1，y_1)\) 是一个空单元格；
• 要么 \(x_0 = x_1\) 且 \(y_0≤y_1\) ，要么 \(x_0≤x_1\) 且 \(y_0 = y_1\) ；
• 单元格 \((x_0，y_0)\) 和 \((x_1，y_1)\) 之间没有墙。

在这些单元格之间可能会有一个守卫，守卫可以互相看到。守卫只能放置在空单元格中（并且只能保护空单元格）。放置守卫的计划是一些单元格的集合，其中将放置守卫。

（如果一个计划中包含至少一个单元格，不包含在第二个计划中，则两个计划是不同的）。

如果没有多于一个未受保护的空单元格，则 zms 称一个计划合适，zms 想知道合适计划的数量。

由于可能非常大，你必须输出它对 \(10^9 + 7\) 取模的结果。

Input Format

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

接下来 n 行，第 i 行包含一个由 m 个字符组成的字符串 - 代表矩阵的第 i 行。每个字符要么是 '.' 或者 'x' 。

Output Format

输出以 \(10^9 + 7\) 为模的合适方案的个数。

Test Case 1

input

1 3
.x.

output

3

Test Case 2

input

2 2
xx
xx

output

1

Note

在第一个例子中，你必须至少安排一名守卫，所以有三种可能的安排:一名守卫在 (1, 1) ，一名守卫在(1, 3) ，两个都有两名守卫。