Рик не сильно любит проводить время со своим внуком Морти вне приключений, однако иногда выделяет немного своего времени для игры в морской бой (разумеется, с настоящими космическими кораблями, а не на бумажке).
Поле для игры в Морской бой состоит из клеток и имеет ширину $$$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
2
3 3.oox...xx0 2 0
1