You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

语言（$\texttt {lang}$）

【题目描述】

小 D 的电脑里有一个 E 语言表达式的计算器，E 语言表达式按如下规则进行运算：

• E 语言由整数，$(,),<,>$ 四种关键字表示。
• 定义 $x<y$ 表示 $\min(x,y)$，$x>y$ 表示 $\max(x,y)$。
• $<,>$ 优先级相同，从左往右依次计算，括号内部的表达式优先计算。

小 D 有一个 E 语言表达式 $E$，所有的整数都是 $n$ 个变量之一，用数码 $0\sim n-1$ 表示变量 $x_{0}\sim x_{n-1}$。

但是这个 E 语言表达式因为宇宙射线的影响，导致一些 $<$ 或 $>$ 变成了 $?$。

对于一组给定的 $x_1\sim x_n$，设 $w$ 为 $?$ 数量，这个计算器会输出 $2^w$ 个可能的表达式的结果之和。

小 D 有 $q$ 组输入的 $x_1\sim x_n$，对于每组输入求出这个计算器的输出。

【输入格式】

从 $\texttt{lang.in}$ 中读入数据。

第一行两个整数 $q,n$。

接下来 $n$ 行，每行 $q$ 个整数，第 $i$ 行第 $j$ 个表示第 $j$ 次询问时 $x_{i-1}$ 的取值。

接下来一行一个字符串表示 $E$。

【输出格式】

输出到 $\texttt{lang.out}$ 中。

$q$ 行每行一个整数，表示第 $i$ 次询问的答案对 $10^9+7$ 取模后的结果。

【样例 1 输入】

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

【样例 1 输出】

5
4

【样例 1 解释】

$?$ 表示 $<$ 时第一组询问答案为 $2$，第二组询问答案为 $1$。

$?$ 表示 $>$ 时第一组询问答案为 $3$，第二组询问答案为 $3$。

【样例 2 输入】

3 3
4 9 2
2 8 1
5 3 7
1?0>2?0

【样例 2 输出】

18
35
18

【样例 3 输入】

5 3
454 351 714 455 897
678 995 544 615 734
671 324 703 926 342
2<(0>2)<0>(1>2)>((0<0)<1>2)<0

【样例 3 输出】

454
351
703
455
734

【样例 4】

见下发文件中的 $\texttt{lang4.in}$ 与 $\texttt{lang4.ans}$。

【数据范围】

对于所有的测试数据有：$1\le n\le10,1\le q,|E|\le 5\times 10^4,1\le x_{i,j}\le 10^9$。

特殊性质 $\text A$：$E$ 中不包含 $?$。

特殊性质 $\text B$：$E$ 中不包含 $(,)$。