Bessie 成为了一名艺术家，正在创作洞穴画！她目前正在创作一个高度为 $N$ 的网格，其中每一行包含 $M$ 个方格（$1\le N,M\le 1000$）。每个方格要么是空的，要么填满了岩石，要么填满了水。Bessie 已经画好了包含岩石的方格，包括画作的整个边界。她现在想在一些空方格中填入水，使得如果这幅画是真实的，水就不会产生净运动。定义从顶部数第 $i$ 行的方格高度为 $N+1-i$。Bessie 希望她的画满足以下约束：

假设方格 $a$ 中填满了水。那么，如果存在一条从 $a$ 到方格 $b$ 的路径，路径仅经过不高于 $a$ 的空方格或水方格，且路径上每两个相邻方格共享一条边，则 $b$ 也必须填满水。

求 Bessie 可以创作出的不同画作数量，结果对 $10^9+7$ 取模。Bessie 可以选择填充任意数量的空方格，包括不填充或全部填充。

子任务

• 测试点 1-5 满足 $N,M\le 10$。
• 测试点 6-15 满足无额外约束。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$。

接下来的 $N$ 行输入每行包含 $M$ 个字符。每个字符要么是 '.'，要么是 '#'，分别代表空方格和填满岩石的方格。第一行、最后一行以及第一列和最后一列仅包含 '#'。

输出格式

一个整数：满足约束的画作数量，对 $10^9+7$ 取模。

样例

样例输入 1

4 9
#########
#...#...#
#.#...#.#
#########

样例输出 1

9

说明

如果第二行中的某个方格被填满水，则所有空方格都必须被填满水。否则，假设没有这样的方格被填满水。那么 Bessie 可以选择填充第三行中三个水平连续空方格区域的任意子集。因此，画作的数量等于 $1+2^3=9$。

题目来源：Daniel Zhang