Array Expression Evaluation with Ambiguous Operators

We are given ( m ) arrays ( A_0, A_1, \ldots, A_{m-1} ), each of length ( n ). An expression ( E ) is provided that is formed using these arrays as operands and the binary operators ( < ) and ( > ). For two arrays ( A ) and ( B ) (both of length ( n )), the binary operator definitions are as follows:

[ \begin{aligned} (A < B)[i] &= \min(A[i], B[i]) \quad (1 \le i \le n), \ (A > B)[i] &= \max(A[i], B[i]) \quad (1 \le i \le n). \end{aligned} ]

In the expression ( E ), every operand is one of ( A_0, A_1, \ldots, A_{m-1} ), and the only operators present are ( < ) and ( > ) (which have the same precedence and are evaluated from left to right). Additionally, the expression may contain the operator ? which stands for an ambiguous operator that can be interpreted either as ( < ) or ( > ). If there are ( t ) occurrences of ? in ( E ), then ( E ) represents ( 2^t ) distinct concrete expressions. Each concrete expression, when evaluated, yields an array of length ( n ) (by performing the operations element-wise). The task is to compute the sum of all elements across all ( 2^t ) resulting arrays and output this sum modulo ( 10^9+7 ).

Note: The operators ( < ) and ( > ) are evaluated in a left-to-right manner. That is, if the expression is written as

[ O_0 ; op_1 ; O_1 ; op_2 ; O_2 ; \cdots ; op_k ; O_k, ]

then the evaluation is done as follows:

1. Let ( R_0 = O_0 ).
2. For ( i = 1 ) to ( k ):
   • If ( op_i = < ), then ( R_i = \min(R_{i-1}, O_i) ).
   • If ( op_i = > ), then ( R_i = \max(R_{i-1}, O_i) ).
   • If ( op_i = ? ), then consider both cases: ( R_i = \min(R_{i-1}, O_i) ) and ( R_i = \max(R_{i-1}, O_i) ).

The final value of the expression is ( R_k ), an array of length ( n ) whose ( i^{th} ) entry is the result computed element-wise across the ( n ) positions.

Your task is to output the sum of all elements from all ( 2^t ) concrete evaluations of ( E ) modulo (10^9+7).

inputFormat

The first line contains two integers \( m \) and \( n \) separated by a space.

Then, \( m \) lines follow, each containing \( n \) integers. The \( i^{th} \) of these lines represents the array \( A_{i} \) (\( 0 \le i \le m-1 \)).

The last line of input is a string representing the expression \( E \). The expression contains operands which are denoted by A0, A1, ..., A{m-1} and operators which can be either <, > or ?. Operators and operands are separated by spaces.

outputFormat

Output a single integer: the sum of all elements over all resulting arrays obtained by resolving every `?` in the given expression, modulo \( 10^9+7 \).

sample

2 3
1 2 3
4 5 6
A0 < A1

6