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$, where $C[i] = \min(A[i], B[i])$ ($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$, where $C[i] = \max(A[i], B[i])$ ($1 \le i \le n$).

There are $m$ ($1 \le m \le 10$) integer arrays $A_0, A_1, \dots, A_{m-1}$, each of length $n$. Given an expression $E$ to be evaluated, where every operand in $E$ is one of $A_0, A_1, \dots, A_{m-1}$, and $E$ contains only the operators < and > (which 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 indicates that the operator could be either < or >. Therefore, if the expression contains $t$ question marks, it can generate $2^t$ expressions with determined values, resulting in $2^t$ result arrays. Your task is to calculate the sum of all elements in these $2^t$ result arrays. You only need to output the sum of all elements modulo $10^9 + 7$.

Input

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 contain $n$ space-separated integers. The $j$-th element of the $i$-th line 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 through 9, (, ), <, >, and ?. The digit characters represent the index of the operand; for example, the character 2 represents the operand $A_2$ in the expression.

Output

A single integer representing the sum of all elements of the results of all $2^t$ expressions, modulo $10^9 + 7$.

Examples

Input 1

1 2
3 1
2 2
1>2?0

Output 1

9

Note 1

The expressions generated by $E$ are: 1. $A_1 > A_2 < A_0$, which results in $[2, 1]$. 2. $A_1 > A_2 > A_0$, which results in $[3, 3]$. The answer is $2 + 1 + 3 + 3 = 9$.

Input 2

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

Output 2

36

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)

Output 3

4276

Input 4

See expr/expr4.in and expr/expr4.ans in the contestant directory.

Constraints

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$.

The specific constraints for each test case are as follows: