海战

题目描述

瑞克并不太喜欢在冒险之外和孙子莫蒂一起度过时间，但有时他会抽出一点时间玩海战（当然是用真正的宇宙飞船，而不是在纸上）。

海战游戏的场地由格子组成，宽度为 $w$，高度为 $h$。战舰可以由一个、两个或三个连续排列的格子组成（水平或垂直）。场地上总共有 $s_1$ 个单格战舰，$s_2$ 个两格战舰和 $s_3$ 个三格战舰。战舰之间不能有边接触或重叠，但可以有角接触。

莫蒂怀疑他那天才的爷爷想尽快获胜，因此他在游戏过程中逐步布置战舰。他已经进行了若干次射击，场地上标记了他射击过的格子以及命中结果：要么该格子里肯定有战舰，要么肯定没有。请帮助他确定瑞克还有多少种可能的战舰摆放方案。因为这个数字可能非常大，所以请输出其对 $10^9 + 7$ 取模的结果。

第一行包含两个整数 $w$ 和 $h$——游戏场地的宽度和高度（$w \le 100$；$h \le 8$）。

接下来的 $h$ 行描述了场地的每一行。字符 . 表示莫蒂没有射击过的格子，o 表示没有战舰的格子（未命中），而 x 表示命中战舰的格子。

最后一行包含三个整数 $s_1$、$s_2$ 和 $s_3$——需要放置在场地上的每种尺寸战舰的数量（$s_1 \le 5$；$s_2 \le 4$；$s_3 \le 3$）。

输出一个整数——瑞克满足给定信息的不同战舰摆放方案的数量，对 $10^9 + 7$ 取模。

两种摆放方案视为不同，如果存在一个格子，在其中一种方案中被战舰占据，而在另一种方案中是空的。

输入：

4 2
.ox.
x.o.
2 1 0

输出：

输入：

3 3
.oo
x..
.xx
0 2 0

输出：