P15908 [TOPC 2024] Disbursement on Quarantine Policy

:::epigraph[《隔离政$ $策》，2023 年 ICPC 桃园区域赛，问题 D] 2019 新型冠状病毒（COVID-19）可通过飞沫和密切接触在人与人之间传播。在相对拥挤或密闭的空间（如飞机或火车）中，传播尤其容易且迅速。如果有人感染了 COVID-19，那么相邻座位的乘客将很容易被感染。 ::: 有一列火车，共有 $n$ 排，每排有 $m$ 个座位。所有座位均有人乘坐。对于部分乘客，我们已知他们是否感染了 COVID-19；但对于其他乘客，我们不确定他们的感染状态，并假设每个人有 $\frac{1}{2}$ 的概率被感染，且相互独立。 所有被感染的乘客需要隔离 $d_0$ 天。所有未感染但与任意感染者有边相邻的乘客，需要隔离 $d_1$ 天。所有未感染、不与任何感染者有边相邻、但与任意感染者有角相邻的乘客，需要隔离 $d_2$ 天。 乘客在隔离期间需要住在酒店。根据规定，政$ $府需要支付酒店费用。作为政$ $府的会计，你需要评估乘客所需隔离的总天数的期望值，这表示政$ $府在酒店费用上的预期总支出。 例如，假设 $n = 4$，$m = 4$，$d_0 = 15$，$d_1 = 7$，$d_2 = 3$。第三行第三列的乘客被感染，我们不知道第一行第二列的乘客是否被感染。其余 14 名乘客未感染。 如果第一行第二列的乘客被感染，则隔离总天数为 91： ``` 7 15 7 0 3 7 7 3 0 7 15 7 0 3 7 3 ``` 如果该乘客未被感染，则隔离总天数为 55： ``` 0 0 0 0 0 3 7 3 0 7 15 7 0 3 7 3 ``` 因此，隔离总天数的期望值为 $\frac{91+55}{2} = 73$。

第一行包含五个整数 $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 \mod 10^9 + 7$，则 $x$ 是 $q$ 在模 $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$ 翻译由 DeepSeek V3.2 完成