Disbursement on Quarantine Policy

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.

There is a train with $n$ rows, and there are $m$ seats per row. All seats are occupied. For some passengers, we know whether they are infected. For the others, we are not sure, so we assume each of them has a $\frac{1}{2}$ chance of being infected, independently of each other.

All infected passengers must be quarantined for $d_0$ days. Passengers who are not infected but are edge-adjacent to an infected passenger must be quarantined for $d_1$ days. Passengers who are not infected, are not edge-adjacent to any infected passenger, but are corner-adjacent to one must be quarantined for $d_2$ days.

Passengers must stay in a hotel during quarantine, and the government pays for the hotel. As an accountant for the government, find the expected total number of quarantine days, which is the expected total hotel cost.

Source: Quarantine Policy, 2023 ICPC Taoyuan Regional Contest, Problem D

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

Print the expected total number of quarantine days modulo $10^9 + 7$. The answer can be written as an irreducible fraction $\frac{p}{q}$, where $q$ is not a multiple of $10^9 + 7$. Print $p \times q^{-1}$ modulo $10^9 + 7$, where $q^{-1}$ is the multiplicative inverse of $q$ modulo $10^9 + 7$. That is, $x$ is the multiplicative inverse of $q$ if $x \times q \equiv 1 \pmod{10^9 + 7}$.

$1 \le n \le 100$

$1 \le m \le 100$

$0 \le d_2 \le d_1 \le d_0 \le 100$