Bob is playing with array expressions!

Bob has ~M~ (~1 \le M \le 10~) arrays, denoted as ~A_0~, ~A_1~, ~\ldots~, ~A_{M-1}~, and each array has ~N~ integers. The index of each array goes from ~1~ to ~N~.

Bob defines two operations between arrays:

• ~C = A < B~ means: ~C[i] = \min{(A[i], B[i])}~ for all ~i~ from ~1~ to ~N~.
• ~C = A > B~ means: ~C[i] = \max{(A[i], B[i])}~ for all ~i~ from ~1~ to ~N~.

These operators have equal precedence, and parentheses () can be used to control evaluation order.

Bob writes down an array expression ~E~, where each operand is one of the ~M~ arrays, the operator is either < or >. Bob may add some parentheses, ( and ), to change the precedence. The result of the expression ~E~ will be a new array with ~N~ integers.

However, Alice comes along and changes some of the < or > operators into ?, which means the operator could be either < or >. If Alice changes ~k~ operators to ?, the expression will have ~2^k~ possible evaluations, each resulting in a different array.

Your task is to evaluate all possible arrays and compute the sum of all their elements, over all ~2^k~ possible expressions. Since the result can be very large, print it modulo ~\mod 10^9 + 7~

Input Specification

The first line of the input contains two integers, ~N~ and ~M~, (~1 \le N \le 5 \times 10^4~, ~1 \le M \le 10~) the length of each array and the number of arrays.

Each of the following ~M~ lines contains ~N~ integers, ~A[i][j]~ (~0 \le i \le M-1~, ~1 \le j \le N~, ~1 \le A[i][j] \le 10^9~), indicating the ~j~th integer in the ~i~-th array.

The last line contains one string ~E~, (~1 \le |E| \le 5 \times 10^4~), the array expression. ~E~ will only contain the following characters: the digit ~0~ to ~9~, (, ), <, >, and ?. The digit represents the index of the array. For example, ~3~ indicates ~A_3~.

Output Specification

Output one integer, the sum of all possible result arrays ~\mod 10^9 + 7~.

Constraints

Subtask	Points	Additional constraints
~1~	~20~	~N \le 5~, ~|E| \le 10~. No (, ) or ? in ~E~.
~2~	~15~	~N \le 10~, ~|E| \le 100~. No ? in ~E~
~3~	~10~	~N \le 2~, ~|E| \le 5\,000~. No ( or ) in ~E~
~4~	~10~	~N \le 2~, ~|E| \le 5\,000~.
~5~	~15~	~N, |E| \le 5\,000~. No ? in ~E~
~6~	~15~	~N, |E| \le 50\,000~. No ? in ~E~
~7~	~15~	No additional constraints.

Sample Input 1

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

Sample Output 1

9

Explanation for Sample 1

There are two possible result arrays:

• ~A_1 > A_2 < A_0~, the result is ~[2, 1]~
• ~A_1 > A_2 > A_0~, the result is ~[3, 3]~

Thus, the total sum is ~2 + 1 + 3 + 3 = 9~.

Sample Input 2

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

Sample Ouput 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