The game board for "Space Battleship" game consists of cells and has a width of $$$w$$$ and a height of $$$h$$$. Ships can consist of one, two, or three consecutive cells either vertically or horizontally.
In total, there should be $$$s_1$$$ one-cell ships, $$$s_2$$$ two-cell ships, and $$$s_3$$$ three-cell ships on the board. Ships must not touch each other side by side or overlap, but they can touch at the corners.
You have to write a program that helps with anti-cheating, i.e., against players who tactically place ships on the board in real time during the game instead of placing them on the board beforehand.
Given the results of the first shots (several cells with the information either for each of them: there is definitely a ship in that cell, or there is definitely no ship), determine how many possible arrangements of ships there are for the opponent. Since this number can be very large, find it modulo $$$10^9 + 7$$$.
The first line contains two integers $$$w$$$ and $$$h$$$ — the width and height of the game board, respectively ($$$w \le 100$$$; $$$h \le 8$$$).
The next $$$h$$$ lines contain descriptions of the rows of the board. The symbol '.' denotes a cell that you have no information about, 'o' denotes a cell without a ship (a miss), and 'x' denotes a cell where a ship has been hit.
The last line contains the numbers $$$s_1$$$, $$$s_2$$$, and $$$s_3$$$ — the number of ships of each size that need to be placed on the board ($$$s_1 \le 5$$$; $$$s_2 \le 4$$$; $$$s_3 \le 3$$$).
Output a single number — the number of distinct arrangements of the opponent's ships that satisfy the given data, taken modulo $$$10^9 + 7$$$.
Two arrangements are considered different if there is a cell occupied by a ship in one arrangement and free in another.
4 2.ox.x.o.2 1 0
2
3 3.oox...xx0 2 0
1
