题目描述

定义二元操作符 $<$：对于两个长度都为 $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, \ldots , A_{m-1}$。给定一个待计算的表达式 $E$，其满足 $E$ 中出现的每个操作数都是 $A_0, A_1, \ldots , A_{m-1}$ 其中之一，且 $E$ 中只包含 $<$ 和 $>$ 两种操作符（$<$ 和 $>$ 的运算优先级相同），因此该表达式的结果值也将是一个长度为 $n$ 的数组。

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

输入格式

第一行两个整数 $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$ 的值。

样例 1

输入 2 3 3 1 2 2 2 3 1>2?0

text

输出 9

text

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

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

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

样例 2

输入 3 3 4 3 2 2 3 1 2 3 3 1?0>2?0

text

输出 36

text

样例 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)

text

输出 4276

text

样例 4

见附加文件中的 expr4.in 与 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$。

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

| 测试点编号 | $n \le$ | $|E| \le$ | 特殊限制 | |------------|---------|----------|----------| | $1 \sim 4$ | $5$ | $10$ | $S$ 中不包含左右括号和问号 | | $5 \sim 7$ | $10$ | $100$ | $S$ 中不包含问号 | | $8 \sim 9$ | $2$ | $5000$ | $S$ 中不包含左右括号 | | $10 \sim 11$ | | | 无 | | $12 \sim 14$ | $5000$ | | $S$ 中不包含问号 | | $15 \sim 17$ | $5 \times 10^4$ | | | | $18 \sim 20$ | | | 无 |