说明

:::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$ 意义下的乘法逆元。

4 4 15 7 3
.?..
....
..V.
....

73

22111
??
??

750000009

提示

• $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 完成