供电网络包含 $n$ 个节点，节点之间通过若干条双向输送线路相连，构成一张无向图。

在配置网络时，所有节点将被分配至两个独立的主供电模块中。对于节点 $i$ ($1 \le i \le n$)，定义其同模块邻点数 $d_i$ 为：在节点 $i$ 所接入的供电模块内，与其有直接线路连接的节点数量。

小 S 共找出了 $q$ 次测试的记录，每次测试的记录通过一个长度为 $n$ 的字符串 $s$ 来表示。对于第 $i$ ($1 \le i \le n$) 个节点：

• 若 $s_i = 0$，则要求在该配置下节点 $i$ 的同模块邻点数 $d_i$ 为偶数；
• 若 $s_i = 1$，则要求在该配置下节点 $i$ 的同模块邻点数 $d_i$ 为奇数；
• 若 $s_i = ?$，则记录中不涉及节点 $i$，即对节点 $i$ 的同模块邻点数奇偶性不作要求。

小 T 指出，记录中涉及的节点集合呈现出规整的嵌套关系。具体而言，设第 $i$ ($1 \le i \le q$) 份测试涉及的节点集合为 $S_i$（即对应字符串中所有不为 $?$ 的位置构成的集合），则对于任意两份不同的测试记录 $i, j$ ($1 \le i < j \le q$)，$S_i$ 和 $S_j$ 必定满足以下三种关系之一：$S_i \subseteq S_j$，$S_j \subseteq S_i$，或 $S_i \cap S_j = \emptyset$。

为了尽快配置好供电网络，你需要协助小 T 和小 S 求出，每次测试中将所有节点接入两个主模块的本质不同方案数。两个方案被视为不同，当且仅当存在至少一个节点，在两套方案中被接入了不同的主模块。由于答案可能很大，你只需要求出其对 $10^9 + 7$ 取模后的结果。

入力

输入的第一行包含两个正整数 $n, q$ ($1 \le n, q \le 3 \times 10^3$)。

接下来 $n$ 行，每行包含一个长度为 $n$ 的 01 字符串，其中第 $i$ ($1 \le i \le n$) 行的第 $j$ ($1 \le j \le n$) 位表示节点 $i$ 与节点 $j$ 间是否存在输送线路，若存在则为 1，否则为 0。保证不存在连接自身的输送线路，即第 $i$ ($1 \le i \le n$) 行的第 $i$ 位一定为 0。

接下来 $q$ 行，每行包含一个长度为 $n$ 的字符串 $s$，表示一次测试的记录。

出力

输出 $q$ 行，每行一个非负整数，表示该次测试中将所有节点接入两个主模块的本质不同方案数对 $10^9 + 7$ 取模后的结果。

入出力例

入力 1

3 2
010
100
000
1?0
010

出力 1

4
0

注記 1

对于第一次测试，共有以下四种接入方案： 1. 将所有节点接入第一个主模块； 2. 将所有节点接入第二个主模块； 3. 将节点 1, 2 接入第一个主模块，将节点 3 接入第二个主模块； 4. 将节点 1, 2 接入第二个主模块，将节点 3 接入第一个主模块。

入力 2

6 5
000010
000001
000000
000001
100000
010100
?11?0?
??????
?10?1?
??0?0?
?01?01

出力 2

0
64
16
32
0