La red eléctrica consta de $n$ nodos, conectados entre sí por varias líneas de transmisión bidireccionales, formando un grafo no dirigido.

Al configurar la red, todos los nodos se asignarán a dos módulos de suministro eléctrico principales independientes. Para el nodo $i$ ($1 \le i \le n$), definimos su número de nodos adyacentes en el mismo módulo, $d_i$, como la cantidad de nodos conectados directamente a él que se encuentran en el mismo módulo de suministro eléctrico al que está conectado el nodo $i$.

Xiao S ha encontrado registros de $q$ pruebas, donde cada registro se representa mediante una cadena $s$ de longitud $n$. Para el nodo $i$ ($1 \le i \le n$): Si $s_i = 0$, se requiere que en esta configuración el número de nodos adyacentes en el mismo módulo $d_i$ para el nodo $i$ sea par. Si $s_i = 1$, se requiere que en esta configuración el número de nodos adyacentes en el mismo módulo $d_i$ para el nodo $i$ sea impar. * Si $s_i = ?$, el registro no involucra al nodo $i$, es decir, no hay requisitos sobre la paridad del número de nodos adyacentes en el mismo módulo para el nodo $i$.

Xiao T señala que los conjuntos de nodos involucrados en los registros presentan una relación de anidamiento regular. Específicamente, sea $S_i$ el conjunto de nodos involucrados en la $i$-ésima prueba ($1 \le i \le q$) (es decir, el conjunto formado por todas las posiciones en la cadena correspondiente que no son '?'). Entonces, para cualquier par de registros de prueba distintos $i, j$ ($1 \le i < j \le q$), $S_i$ y $S_j$ deben satisfacer una de las siguientes tres relaciones: $S_i \subseteq S_j$, $S_j \subseteq S_i$, o $S_i \cap S_j = \emptyset$.

Para configurar la red eléctrica lo antes posible, necesitas ayudar a Xiao T y a Xiao S a calcular, para cada prueba, el número de formas esencialmente distintas de conectar todos los nodos a los dos módulos principales. Dos soluciones se consideran distintas si y solo si existe al menos un nodo que esté conectado a un módulo principal diferente en las dos soluciones. Dado que la respuesta puede ser muy grande, solo necesitas calcular el resultado módulo $10^9 + 7$.

Entrada

La primera línea de la entrada contiene dos enteros positivos $n, q$ ($1 \le n, q \le 3 \times 10^3$).

A continuación, $n$ líneas, cada una contiene una cadena de $01$ de longitud $n$, donde el $j$-ésimo carácter ($1 \le j \le n$) de la $i$-ésima línea ($1 \le i \le n$) indica si existe una línea de transmisión entre el nodo $i$ y el nodo $j$; si existe, es $1$, de lo contrario es $0$. Se garantiza que no existen líneas de transmisión que se conecten a sí mismas, es decir, el $i$-ésimo carácter de la $i$-ésima línea es siempre $0$.

A continuación, $q$ líneas, cada una contiene una cadena $s$ de longitud $n$, que representa el registro de una prueba.

Salida

Imprime $q$ líneas, cada una con un entero no negativo que representa el número de formas esencialmente distintas de conectar todos los nodos a los dos módulos principales para esa prueba, módulo $10^9 + 7$.

Ejemplos

Entrada 1

3 2
010
100
000
1?0
010

Salida 1

4
0

Nota 1

Para la primera prueba, existen las siguientes cuatro soluciones: 1. Conectar todos los nodos al primer módulo principal. 2. Conectar todos los nodos al segundo módulo principal. 3. Conectar los nodos 1 y 2 al primer módulo principal, y el nodo 3 al segundo módulo principal. 4. Conectar los nodos 1 y 2 al segundo módulo principal, y el nodo 3 al primer módulo principal.

Entrada 2

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

Salida 2

0
64
16
32
0