The power network consists of $n$ nodes, connected by several bidirectional transmission lines, forming an undirected graph.

When configuring the network, all nodes will be assigned to two independent main power modules. For a node $i$ ($1 \le i \le n$), define its "same-module neighbor count" $d_i$ as the number of nodes directly connected to node $i$ that are assigned to the same power module as node $i$.

Small S has found $q$ test records, where each record is represented by a string $s$ of length $n$. For the $i$-th node ($1 \le i \le n$): If $s_i = 0$, it is required that the same-module neighbor count $d_i$ for node $i$ in this configuration be even. If $s_i = 1$, it is required that the same-module neighbor count $d_i$ for node $i$ in this configuration be odd. * If $s_i = ?$, the record does not involve node $i$, meaning there is no parity requirement for the same-module neighbor count of node $i$.

Small T points out that the sets of nodes involved in the records exhibit a regular nested structure. Specifically, let $S_i$ be the set of nodes involved in the $i$-th test record ($1 \le i \le q$) (i.e., the set of positions in the corresponding string that are not $?$). Then, for any two different test records $i, j$ ($1 \le i < j \le q$), $S_i$ and $S_j$ must satisfy one of the following three relationships: $S_i \subseteq S_j$, $S_j \subseteq S_i$, or $S_i \cap S_j = \emptyset$.

To configure the power network as quickly as possible, you need to assist Small T and Small S in calculating the number of essentially different ways to connect all nodes to the two main modules for each test. Two schemes are considered different if and only if there exists at least one node that is connected to a different main module in the two schemes. Since the answer can be very large, you only need to output the result modulo $10^9 + 7$.

Input

The first line contains two positive integers $n, q$ ($1 \le n, q \le 3 \times 10^3$).

The next $n$ lines each contain a binary string of length $n$, where the $j$-th character of the $i$-th line ($1 \le i, j \le n$) indicates whether there is a transmission line between node $i$ and node $j$. If it exists, it is $1$, otherwise it is $0$. It is guaranteed that there are no transmission lines connecting a node to itself, i.e., the $i$-th character of the $i$-th line is always $0$.

The next $q$ lines each contain a string $s$ of length $n$, representing a test record.

Output

Output $q$ lines, each containing a non-negative integer representing the number of essentially different ways to connect all nodes to the two main modules for that test, modulo $10^9 + 7$.

Examples

Input 1

3 2
010
100
000
1?0
010

Output 1

4
0

Note

For the first test, there are the following four connection schemes: 1. Connect all nodes to the first main module; 2. Connect all nodes to the second main module; 3. Connect nodes 1 and 2 to the first main module, and node 3 to the second main module; 4. Connect nodes 1 and 2 to the second main module, and node 3 to the first main module.

Input 2

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

Output 2

0
64
16
32
0