P7324 [WC2021] Expression Evaluation

Define the binary operator ``$B$ is also an array of length $n$, denoted by $C$. Then $C[i] = \max(A[i], B[i])$ ($1 \le i \le n$). Now there are $m$ ($1 \le m \le 10$) integer arrays $A_0, A_1, \ldots , A_{m-1}$, all of length $n$. You are given an expression $E$ to evaluate. Every operand in $E$ is one of $A_0, A_1, \ldots , A_{m-1}$, and $E$ contains only the two operators `` (they have the same precedence). Therefore, the value of this expression is also an array of length $n$. In particular, the expression $E$ may also contain the operator `?`, which means this operator may be ``. Thus, if the expression contains $t$ `?` characters, it can generate $2^t$ fully determined expressions, producing $2^t$ results (each result is an array). Your task is to compute the sum of all elements across these $2^t$ result arrays. You only need to output this total sum modulo ${10}^9 + 7$.

The first line contains two integers $n, m$, representing the array length and the number of arrays. Lines $2$ to $m + 1$ each contain $n$ integers separated by spaces. The $j$-th number on line $i$ represents $A_{i-2}[j]$ ($2 \le i \le m + 1$, $1 \le j \le n$). The last line contains a string $S$, representing the expression $E$. $S$ contains only the characters `0` to `9`, `(`, `)`, ``, `?`. A digit character indicates the index of an operand; for example, character `2` means the operand is $A_2$.

Output a single integer: the sum of all elements in the results of the $2^t$ expressions, modulo ${10}^9 + 7$.

**Sample Explanation #1** The expressions generated by $E$ are: 1. $A_1$`>`$A_2$``$A_2$`>`$A_0$, whose result is $[3, 3]$. So the answer is $2 + 1 + 3 + 3 = 9$. **Constraints** For all test points: $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$. The specific limits for each test point are shown in the table below: | Test Point ID | $n \le$ | $\vert E \vert \le$ | Special Restrictions | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $5$ | $10$ | $S$ does not contain parentheses or question marks | | $5 \sim 7$ | $10$ | $100$ | $S$ does not contain question marks | | $8 \sim 9$ | $2$ | $5000$ | $S$ does not contain parentheses | | $10 \sim 11$ | $2$ | $5000$ | None | | $12 \sim 14$ | $5000$ | $5000$ | $S$ does not contain question marks | | $15 \sim 17$ | $5 \times {10}^4$ | $5 \times {10}^4$ | $S$ does not contain question marks | | $18 \sim 20$ | $5 \times {10}^4$ | $5 \times {10}^4$ | None | Translated by ChatGPT 5