#P1381. Guards In The Storehouse

Guards In The Storehouse

题目描述

给定一个 n×mn\times m 的网格,有些位置是障碍(x),有些位置是空地(.)。

可以在每一个空地处放一个摄像头,这个摄像头会向右,向下监视第一个障碍前的所有方格。现在你需要在空地上安排摄像头,使得最多 11 个空地没有被摄像头监视。输出方案数对 109+710^9+7 取模。

输入格式

第一行两个整数 n,mn,m1n,m2501\le n,m\le 2501nm2501\le nm\le 250

接下来 nn 行,每行 mm 个字符。

输出格式

一个整数表示答案,对 109+710^9+7 取模。

1 3
.x.
3
2 2
xx
xx
1
2 2
..
..
10
3 1
x
.
x
2