P7324 [WC2021] 表达式求值

定义二元操作符 ``$B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \max(A[i], B[i])$（$1 \le i \le n$）。 现在有 $m$（$1 \le m \le 10$）个长度均为 $n$ 的整数数组 $A_0, A_1, \ldots , A_{m-1}$。给定一个待计算的表达式 $E$，其满足 $E$ 中出现的每个操作数都是 $A_0, A_1, \ldots , A_{m-1}$ 其中之一，且 $E$ 中只包含 `` 两种操作符（`` 的运算优先级相同），因此该表达式的结果值也将是一个长度为 $n$ 的数组。 特殊地，表达式 $E$ 中还可能出现操作符 `?`，它表示该运算符可能是 ``。因此若表达式中有 $t$ 个 `?`，则该表达式可生成 $2^t$ 个可求确定值的表达式，从而可以得到 $2^t$ 个结果值，你的任务就是求出这 $2^t$ 个结果值（每个结果都是一个数组）中所有的元素的和。你只需要给出所有元素之和对 ${10}^9 + 7$ 取模后的值。

无

无

**【样例解释 #1】** 表达式 $E$ 生成的算式有： 1. $A_1$`>`$A_2$``$A_2$`>`$A_0$，其结果为 $[3, 3]$。 答案为 $2 + 1 + 3 + 3 = 9$。 **【数据范围】** 对于所有测试点：$1 \le n \le 5 \times {10}^4$，$1 \le m \le 10$，$|S| \le 5 \times {10}^4$，$1 \le A_i[j] \le {10}^9$。 每个测试点的具体限制见下表： | 测试点编号 | $n \le$ | $\vert E \vert \le$ | 特殊限制 | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $5$ | $10$ | $S$ 中不包含左右括号和问号 | | $5 \sim 7$ | $10$ | $100$ | $S$ 中不包含问号 | | $8 \sim 9$ | $2$ | $5000$ | $S$ 中不包含左右括号 | | $10 \sim 11$ | $2$ | $5000$ | 无 | | $12 \sim 14$ | $5000$ | $5000$ | $S$ 中不包含问号 | | $15 \sim 17$ | $5 \times {10}^4$ | $5 \times {10}^4$ | $S$ 中不包含问号 | | $18 \sim 20$ | $5 \times {10}^4$ | $5 \times {10}^4$ | 无 |