D. Disbursement on Quarantine Policy
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
The 2019 novel coronavirus, COVID-19, can be transmitted between humans through water droplets and close contact. The transmission is especially easy and fast in relatively crowded or confined spaces, such as airplanes or trains. If someone is infected with COVID-19, then passengers occupying the adjacent seats will be infected easily.
—"Quarantine Policy," 2023 ICPC Taoyuan Regional Contest, Problem D

There is a train with $$$n$$$ rows, and there are $$$m$$$ seats per row. All seats are occupied. For some passengers, we know they are being infected with COVID-19 or not. However, for other passengers, we are not sure about their status, and we assume each of them has $$$\frac{1}{2}$$$ chance being infected with COVID-19, independent from each other.

All infected passengers need to be quarantined for $$$d_0$$$ days. All passengers that are not infected, but edge-adjacent to any infected passenger, need to be quarantined for $$$d_1$$$ days. All passengers that are not infected, not edge-adjacent to any infected passenger, but corner-adjacent to any infected passenger, need to be quarantined for $$$d_2$$$ days.

The passengers need to stay in the hotel during quarantine. According to the regulations, the government needs to pay for the hotel. As an accountant of the government, you are asked to evaluate the expected total number of days the passengers need to be quarantined, which indicates the expected total cost on paying for the hotel.

For example, suppose $$$n = 4$$$, $$$m = 4$$$, $$$d_0 = 15$$$, $$$d_1 = 7$$$, $$$d_2 = 3$$$. The third passenger in the third row is infected, and we don't know whether the second passenger in the first row is infected or not. Other 14 passengers are not infected.

If the second passenger in the first row is infected, then the total number of days of quarantine is $$$91$$$: 


7 15  7  0
3  7  7  3
0  7 15  7
0  3  7  3

If that passenger is not infected, then the total number of days of quarantine is $$$55$$$: 


0  0  0  0
0  3  7  3
0  7 15  7
0  3  7  3

So the expected total number of days of quarantine is $$$\frac{91 + 55}{2} = 73$$$.

Input

The first line contains five integers $$$n$$$, $$$m$$$, $$$d_0$$$, $$$d_1$$$ and $$$d_2$$$. The following $$$n$$$ lines contain $$$m$$$ characters each. The $$$j$$$-th character of the $$$i$$$-th line represents the passenger occupying the $$$j$$$-th seat of the $$$i$$$-th row. Each character is one of 'V', '.', or '?'. 'V' means an infected passenger, '.' means a not infected passenger, and '?' means a passenger that has $$$\frac{1}{2}$$$ chance being infected.

Technical Specification

  • $$$1 \le n \le 100$$$
  • $$$1 \le m \le 100$$$
  • $$$0 \le d_2 \le d_1 \le d_0 \le 100$$$
Output

The expected total number of days the passengers need to be quarantined, modulo $$$10^9+ 7$$$. It can be proved that the answer can be represented by a rational number $$$\frac{p}{q}$$$ where $$$q$$$ is not a multiple of $$$10^9 + 7$$$. Then you need to print $$$p \times q^{-1}$$$ modulo $$$10^9 + 7$$$, where $$$q^{-1}$$$ means the multiplicative inverse of $$$q$$$ modulo $$$10^9+7$$$.

Note: If $$$x\times q\equiv 1\mod 10^9+7$$$, then $$$x$$$ is the multiplicative inverse of $$$q$$$ modulo $$$10^9+7$$$.

Examples
Input
4 4 15 7 3
.?..
....
..V.
....
Output
73
Input
2 2 1 1 1
??
??
Output
750000009