“2019新型冠状病毒（COVID-19）可以通过飞沫和密切接触在人与人之间传播。在飞机或火车等相对拥挤或封闭的空间中，传播尤为容易和迅速。如果有人感染了 COVID-19，那么坐在相邻座位的乘客很容易被感染。” ——“Quarantine Policy,” 2023 ICPC Taoyuan Regional Contest, Problem D

有一列火车，共有 $n$ 排，每排有 $m$ 个座位。所有座位都已坐满。对于某些乘客，我们知道他们是否感染了 COVID-19。然而，对于其他乘客，我们无法确定他们的状态，并假设他们每个人都有 $\frac{1}{2}$ 的概率感染了 COVID-19，且彼此之间相互独立。

所有被感染的乘客需要隔离 $d_0$ 天。所有未被感染、但与任何被感染乘客边相邻（edge-adjacent）的乘客需要隔离 $d_1$ 天。所有未被感染、不与任何被感染乘客边相邻、但与任何被感染乘客角相邻（corner-adjacent）的乘客需要隔离 $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} \bmod (10^9 + 7)$，其中 $q^{-1}$ 表示 $q$ 模 $10^9 + 7$ 的乘法逆元。

注：如果 $x \times q \equiv 1 \pmod{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$

样例

输入样例 1

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

输出样例 1

73

输入样例 2

2 2 1 1 1
??
??

输出样例 2

750000009