定义二元操作符 <：对于两个长度都为 $n$ 的数组 $A,B$（下标从 $1$ 到 $n$），$A$<$B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i]=min(A[i],B[i])$（$1\le i\le n$）。

定义二元操作符 >：对于两个长度都为 $n$ 的数组 $A,B$（下标从 $1$ 到 $n$），$A$>$B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i]=max(A[i],B[i])$（$1\le i\le n$）。

现在有 $m$（$1\le m\le 10$）个长度均为 $n$ 的整数数组 $A_0,A_1,\dots ,A_{m-1}$。给定一个待计算的表达式 $E$，其满足 $E$ 中出现的每个操作数都是 $A_0,A_1,\dots ,A_{m-1}$ 其中之一，且 $E$ 中只包含 < 和 > 两种操作符（< 和 > 的运算优先级相同），因此该表达式的结果值也将是一个长度为 $n$ 的数组。

特殊地，表达式 $E$ 中还可能出现操作符 ?，它表示该运算符可能是 < 也可能是 >。因此若表达式中有 $t$ 个 ?，则该表达式可生成 $2^t$ 个可求确定值的表达式，从而可以得到 $2^t$ 个结果值，你的任务就是求出这 $2^t$ 个结果值（每个结果都是一个数组）中所有的元素的和。你只需要给出所有元素之和对 ${10}^9+7$ 取模后的值。

我们定义表达式如下：

1. 一个长度为 $n$ 的数组 A 是表达式。

2. 如果 A 是表达式，那么 (A) 也是表达式。

3. 如果 A 是表达式，B 是一个长度为 $n$ 的数组，那么 A?B,A<B,A>B 也是表达式。

4. 如果 A 和 B 是表达式，那么 A?(B), A<(B), A>(B) 也是表达式。

输入格式

第一行两个整数 $n,m$，分别表示数组长度与数组个数。

第 $2\sim m+1$ 行每行 $n$ 个用空格分隔的整数，第 $i$ 行第 $j$ 个元素代表 $A_{i-2}[j]$（$2\le i\le m+1$，$1\le j\le n$）。

最后一行一个字符串 $S$，表示表达式 $E$。$S$ 中只包含字符 0 到 9、(、)、<、>、?，数字字符表示操作数的下标，例如字符 2 表示表达式中的操作数为 $A_2$。

输出格式

仅一行一个整数，表示所有 $2^t$ 个表达式的结果，它们的元素之和模 ${10}^9+7$ 的值。

样例一

input

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

output

9

explanation

表达式 $E$ 生成的算式有：

1. $A_1$>$A_2$<$A_0$，其结果为 $[2,1]$。
2. $A_1$>$A_2$>$A_0$，其结果为 $[3,3]$。

答案为 $2+1+3+3=9$。

样例二

input

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

output

36

样例三

input

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

4276

样例四

见附加文件中 ex_expr4.in 与 ex_expr4.ans。

限制与约定

对于所有测试点：$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$。

每个测试点的具体限制见下表：

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载