Problem Description

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

Define the binary operator >: For two arrays $A$ and $B$ of length $n$ (indexed from 1 to $n$), the result of $A$ > $B$ is also an array of length $n$, denoted as $C$. Thus, $C[i] = \max(A[i], B[i])$ for $1 \le i \le n$.

Given $m$ ($1 \le m \le 10$) arrays of integers, each of length $n$, denoted as $A_0, A_1, \ldots, A_{m-1}$. A given expression $E$ is provided, where each operand in $E$ is one of $A_0, A_1, \ldots, A_{m-1}$, and $E$ only contains the operators < and > (< and > have the same precedence). The result of this expression will also be an array of length $n$.

Specifically, the expression $E$ may also contain the operator ?, which means the operator could be either < or >. Therefore, if there are $t$ ? operators in the expression, it can generate $2^t$ determinate expressions, resulting in $2^t$ result arrays. Your task is to find the sum of all elements in these $2^t$ result arrays, and output the sum modulo ${10}^9 + 7$.

Input Format

The first line contains two integers $n$ and $m$, representing the length of the arrays and the number of arrays, respectively.

The next $m$ lines, each containing $n$ integers separated by spaces, represent the arrays $A_0, A_1, \ldots, A_{m-1}$. Specifically, the $j$-th element of the $i$-th line (for $2 \le i \le m + 1$ and $1 \le j \le n$) represents $A_{i-2}[j]$.

The last line contains a string $S$, representing the expression $E$. $S$ only contains characters 0 to 9, (, ), <, >, and ?. Digit characters represent the indices of the operands, e.g., the character 2 represents the operand $A_2$.

Output Format

Output a single integer, which is the sum of all elements in the $2^t$ result arrays modulo ${10}^9 + 7$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

9

Sample Input #2

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

Sample Output #2

36

Sample Input #3

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)

Sample Output #3

4276

Sample Input #4

See attached file expr/expr4.in

Sample Output #4

See attached file expr/expr4.ans

Notes/Hints

Sample Explanation #1

The expression $E$ generates the following expressions:

1. $A_1$ > $A_2$ < $A_0$, resulting in $[2, 1]$.
2. $A_1$ > $A_2$ > $A_0$, resulting in $[3, 3]$.

The answer is $2 + 1 + 3 + 3 = 9$.

Data Range

For all test cases: $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$.

Specific constraints for each test case are as follows:

见题面 Input 部分

见题面 Output 部分