定义二元操作符 <
:对于两个长度都为 $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$ 的数组
A
是表达式。如果
A
是表达式,那么(A)
也是表达式。如果
A
是表达式,B
是一个长度为 $n$ 的数组,那么A?B
,A<B
,A>B
也是表达式。如果
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$ 生成的算式有:
- $A_1$
>
$A_2$<
$A_0$,其结果为 $[2, 1]$。 - $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$。
每个测试点的具体限制见下表:
测试点编号 | $n \le$ | $\vert E \vert \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$ | $5 \times {10}^4$ | |
$18 \sim 20$ | 无 |
时间限制:$1\texttt{s}$
空间限制:$512\texttt{MB}$