CF845F Guards In The Storehouse

Polycarp 在 Berland 首都拥有一家店铺。最近首都的犯罪活动增加了，因此 Polycarp 正在考虑为他的仓库建立更好的安全措施。 这个仓库可以用一个 $n$ 行 $m$ 列的矩阵来表示。矩阵中的每个元素要么是 $.$（空地），要么是 $x$（墙）。 Polycarp 想雇佣一些警卫（可以为零个），守卫仓库。每个警卫将站在矩阵的某个格子里，能够守卫从他所在格子起，向右直到最近的墙、向下直到最近的墙的所有格子。更形式化地说，如果警卫站在格子 $(x_0,y_0)$，他能守卫格子 $(x_1,y_1)$，当且仅当以下条件全部满足： - $(x_1,y_1)$ 是一个空地； - 要么 $x_0 = x_1$ 且 $y_0 \leq y_1$，要么 $x_0 \leq x_1$ 且 $y_0 = y_1$； - 在 $(x_0,y_0)$ 与 $(x_1,y_1)$ 之间没有墙，可以有其他警卫经过，警卫可以“看穿”其他警卫。 警卫只能被放在空地上（且只能守卫空地）。警卫布置方案是指出警卫站在哪些格子的方案（如果有至少一个格子只包含在第一个方案而不在第二个方案，或者反之，则这两个方案不同）。Polycarp 认为一个方案是合适的，如果至多只有一个空地没有被守卫。 Polycarp 想知道有多少种合适的方案。由于答案可能很大，你需要输出对 $10^9+7$ 取模的结果。

第一行包含两个整数 $n$ 和 $m$ —— 仓库的行和列数（$1 \leq n,m \leq 250$，$1 \leq nm \leq 250$）。 接下来 $n$ 行，每行包含一个仅由 $.$ 或 $x$ 组成的长度为 $m$ 的字符串，表示仓库矩阵的第 $i$ 行。

输出合适方案的数量，对 $10^9+7$ 取模。

在第一个样例中，必须至少安排一个警卫，因此有三种可能的方案：一个警卫在 $(1,1)$，一个警卫在 $(1,3)$，或者分别在这两个位置各放一个警卫。 由 ChatGPT 5 翻译