격리 정책에 따른 지출

2019년 신종 코로나바이러스 감염증(COVID-19)은 물방울과 밀접 접촉을 통해 사람 사이에서 전파될 수 있다. 전파는 비행기나 기차처럼 비교적 붐비거나 밀폐된 공간에서 특히 쉽고 빠르게 일어난다. 누군가 COVID-19에 감염되면 옆자리 승객도 쉽게 감염된다.

기차에는 $n$개의 행이 있고, 각 행에는 $m$개의 좌석이 있다. 모든 좌석에는 승객이 앉아 있다. 일부 승객은 감염 여부를 알고 있다. 나머지 승객은 감염 여부를 알 수 없으므로, 각 승객이 감염되었을 확률을 $\frac{1}{2}$로 보고 승객끼리는 서로 독립이라고 가정한다.

감염된 승객은 $d_0$일 동안 격리해야 한다. 감염되지 않았지만 감염된 승객과 변을 맞대고 있는 승객은 $d_1$일 동안 격리해야 한다. 감염되지 않았고 감염된 승객과 변을 맞대고 있지는 않지만 모서리를 맞대고 있는 승객은 $d_2$일 동안 격리해야 한다.

격리 기간 동안 승객은 호텔에 머물러야 하며, 정부가 호텔 비용을 부담한다. 정부 회계 담당자로서 격리 일수의 총합에 대한 기댓값, 즉 호텔 비용의 기댓값을 구하라.

출처: Quarantine Policy, 2023 ICPC Taoyuan Regional Contest, Problem D

첫 줄에 정수 $n$, $m$, $d_0$, $d_1$, $d_2$가 주어진다. 다음 $n$개 줄에는 각각 $m$개의 문자가 주어진다. $i$번째 줄의 $j$번째 문자는 $i$번째 행 $j$번째 좌석의 승객을 나타낸다. 각 문자는 V, ., ? 중 하나이다. V는 감염된 승객, .은 감염되지 않은 승객, ?는 감염 확률이 $\frac{1}{2}$인 승객이다.

격리 일수의 기댓값을 $10^9 + 7$로 나눈 나머지를 출력한다. 답은 기약분수 $\frac{p}{q}$로 나타낼 수 있으며, $q$는 $10^9 + 7$의 배수가 아니다. 이때 $p \times q^{-1}$을 $10^9 + 7$로 나눈 나머지를 출력한다. 여기서 $q^{-1}$은 $q$의 $10^9 + 7$에 대한 곱셈 역원이다. 즉, $x \times q \equiv 1 \pmod{10^9 + 7}$을 만족하는 $x$가 $q$의 곱셈 역원이다.

$1 \le n \le 100$

$1 \le m \le 100$

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