Description

Define the binary operator <: for two arrays $A, B$ of length $n$ (indices from $1$ to $n$), the result of $A$<$B$ is also an array of length $n$, denoted by $C$. Then $C[i] = \min(A[i], B[i])$ ($1 \le i \le n$).

Define the binary operator >: for two arrays $A, B$ of length $n$ (indices from $1$ to $n$), the result of $A$>$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 < and > (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 < or >. 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$.

Input Format

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 Format

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

2 3
3 1
2 2
2 3
1>2?0

9

3 3
4 3 2
2 3 1
2 3 3
1?0>2?0

36

5 3
354 321 414 205 257
458 996 554 635 730
681 374 903 966 349
2<0>2<0>(1>2)>(0<0)

4276

见附件中的 expr/expr4.in

见附件中的 expr/expr4.ans

Hint

Sample Explanation #1

The expressions generated by $E$ are:

1. $A_1$>$A_2$<$A_0$, whose result is $[2, 1]$.
2. $A_1$>$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:

Translated by ChatGPT 5