Le réseau électrique comprend $n$ nœuds, reliés entre eux par plusieurs lignes de transport bidirectionnelles, formant un graphe non orienté.

Lors de la configuration du réseau, tous les nœuds doivent être répartis dans deux modules d'alimentation principaux indépendants. Pour un nœud $i$ ($1 \le i \le n$), on définit son nombre de voisins dans le même module, noté $d_i$, comme le nombre de nœuds connectés directement à $i$ qui sont affectés au même module d'alimentation que $i$.

Xiao S a trouvé $q$ enregistrements de tests, chaque enregistrement étant représenté par une chaîne de caractères $s$ de longueur $n$. Pour le $i$-ième nœud ($1 \le i \le n$) : Si $s_i = 0$, alors le nombre de voisins dans le même module $d_i$ pour le nœud $i$ dans cette configuration doit être pair ; Si $s_i = 1$, alors le nombre de voisins dans le même module $d_i$ pour le nœud $i$ dans cette configuration doit être impair ; * Si $s_i = ?$, alors le nœud $i$ n'est pas concerné par l'enregistrement, c'est-à-dire qu'aucune contrainte de parité n'est imposée sur $d_i$ pour le nœud $i$.

Xiao T souligne que les ensembles de nœuds impliqués dans les enregistrements présentent une relation d'imbrication régulière. Plus précisément, soit $S_i$ l'ensemble des nœuds impliqués dans le $i$-ième test ($1 \le i \le q$) (c'est-à-dire l'ensemble des positions dans la chaîne correspondante qui ne sont pas égales à ?). Alors, pour deux enregistrements de test distincts quelconques $i, j$ ($1 \le i < j \le q$), $S_i$ et $S_j$ satisfont nécessairement l'une des trois relations suivantes : $S_i \subseteq S_j$, $S_j \subseteq S_i$, ou $S_i \cap S_j = \emptyset$.

Afin de configurer le réseau électrique au plus vite, vous devez aider Xiao T et Xiao S à calculer, pour chaque test, le nombre de façons essentiellement différentes d'affecter tous les nœuds aux deux modules principaux. Deux configurations sont considérées comme différentes si et seulement s'il existe au moins un nœud affecté à un module différent dans les deux configurations. Comme la réponse peut être très grande, vous devez seulement donner le résultat modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée contient deux entiers positifs $n, q$ ($1 \le n, q \le 3 \times 10^3$).

Les $n$ lignes suivantes contiennent chacune une chaîne de caractères de longueur $n$ composée de 0 et 1, où le $j$-ième caractère de la $i$-ième ligne ($1 \le i, j \le n$) indique s'il existe une ligne de transport entre le nœud $i$ et le nœud $j$ (1 si elle existe, 0 sinon). Il est garanti qu'il n'existe pas de ligne de transport reliant un nœud à lui-même, c'est-à-dire que le $i$-ième caractère de la $i$-ième ligne est toujours 0.

Les $q$ lignes suivantes contiennent chacune une chaîne de caractères $s$ de longueur $n$, représentant l'enregistrement d'un test.

Sortie

Affichez $q$ lignes, chacune contenant un entier non négatif représentant le nombre de façons essentiellement différentes d'affecter tous les nœuds aux deux modules principaux pour le test correspondant, modulo $10^9 + 7$.

Exemples

Entrée 1

3 2
010
100
000
1?0
010

Sortie 1

4
0

Remarque

Pour le premier test, il existe les quatre configurations suivantes : 1. Affecter tous les nœuds au premier module ; 2. Affecter tous les nœuds au deuxième module ; 3. Affecter les nœuds 1 et 2 au premier module, et le nœud 3 au deuxième module ; 4. Affecter les nœuds 1 et 2 au deuxième module, et le nœud 3 au premier module.

Entrée 2

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

Sortie 2

0
64
16
32
0