#3246. 「USACO 2020.1 Platinum」Cave Paintings

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

题目来自 USACO 2020 January Contest, Platinum Problem 1. Cave Paintings

Bessie 成为了一名艺术家,正在创作壁画!她现在正在创作的作品是一个高为 N 的方阵,方阵的每行都由 M 个方格组成。每个方格是空的,画了石头,或者画了水。Bessie 已经画上了包含石头的方格,包括整幅画作的边界。她现在想要将某些空的方格画上水,使得如果这幅画是真实的,其中应当不存在水的净移动。定义从上到下第 i 行的方格的高度为 N+1−i 。Bessie 想要她的画作满足以下限制:

假设方格 a 画的是水。那么如果存在一条从 a 到方格 b 的路径,由高度不超过 a 的空的方格或是有水的方格组成,路径中每相邻两个方格都有一条公共边,那么 b 画的也是水。

求 Bessie 可以创作的不同作品的数量模 10^9+7 的余数。Bessie 可以将任意数量的空格画上水,包括不画以及全画。

输入格式

输入的第一行包含两个空格分隔的整数 N M

以下 N 行每行包含 M 个字符。每个字符均为 .#,分别表示一个空的方格和一个画有石头的方格。第一行和最后一行、第一列和最后一列仅包含 #

输出格式

输出一个整数,为满足限制的作品的数量模 10^9+7 的余数。

样例

样例输入

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

样例输出

9

样例解释

如果第二行中的任意一个方格被画上水,那么所有空的方格必须都被画上水。否则,假设没有这样的方格画有水。那么 Bessie 可以选择画上第三行的空格组成的三个连续区域的任意子集。所以,画作的总数等于 1+2^3=9

数据范围与提示

对于 100\% 的数据,保证 1\le N, M\le 10^3

其中对于测试点 1\sim5 ,保证 N, M\le 10