Sieć energetyczna składa się z $n$ węzłów, połączonych ze sobą za pomocą pewnej liczby dwukierunkowych linii przesyłowych, tworzących graf nieskierowany.

Podczas konfiguracji sieci wszystkie węzły zostaną przypisane do dwóch niezależnych głównych modułów zasilających. Dla węzła $i$ ($1 \le i \le n$) definiujemy jego liczbę sąsiadów w tym samym module $d_i$ jako: liczbę węzłów połączonych bezpośrednią linią z węzłem $i$, które znajdują się w tym samym module zasilającym co węzeł $i$.

Pan S odnalazł zapisy z $q$ testów, z których każdy jest reprezentowany przez ciąg znaków $s$ o długości $n$. Dla $i$-tego węzła ($1 \le i \le n$): Jeśli $s_i = 0$, wymagane jest, aby w tej konfiguracji liczba sąsiadów węzła $i$ w tym samym module, $d_i$, była parzysta. Jeśli $s_i = 1$, wymagane jest, aby w tej konfiguracji liczba sąsiadów węzła $i$ w tym samym module, $d_i$, była nieparzysta. * Jeśli $s_i = ?$, zapis nie dotyczy węzła $i$, co oznacza, że nie ma wymagań co do parzystości liczby sąsiadów węzła $i$ w tym samym module.

Pan T zauważył, że zbiory węzłów objętych testami wykazują regularną relację zagnieżdżenia. Mówiąc dokładniej, niech $S_i$ będzie zbiorem węzłów objętych $i$-tym testem ($1 \le i \le q$) (czyli zbiorem wszystkich pozycji w odpowiadającym mu ciągu, które nie są równe $?$). Wtedy dla dowolnych dwóch różnych zapisów testowych $i, j$ ($1 \le i < j \le q$), zbiory $S_i$ oraz $S_j$ muszą spełniać jedną z trzech relacji: $S_i \subseteq S_j$, $S_j \subseteq S_i$ lub $S_i \cap S_j = \emptyset$.

Aby jak najszybciej skonfigurować sieć energetyczną, musisz pomóc Panu T i Panu S obliczyć liczbę istotnie różnych sposobów przypisania wszystkich węzłów do dwóch głównych modułów dla każdego testu. Dwa sposoby są uważane za różne wtedy i tylko wtedy, gdy istnieje co najmniej jeden węzeł, który w obu wariantach został przypisany do innego głównego modułu. Ponieważ wynik może być bardzo duży, należy podać go modulo $10^9 + 7$.

Wejście

Pierwsza linia wejścia zawiera dwie dodatnie liczby całkowite $n, q$ ($1 \le n, q \le 3 \times 10^3$).

Następnie $n$ linii, z których każda zawiera ciąg znaków 01 o długości $n$. $j$-ty znak ($1 \le j \le n$) w $i$-tej linii ($1 \le i \le n$) oznacza, czy istnieje linia przesyłowa między węzłem $i$ a węzłem $j$. Jeśli istnieje, wartość wynosi 1, w przeciwnym razie 0. Gwarantuje się, że nie istnieją linie łączące węzeł z samym sobą, tzn. $i$-ty znak w $i$-tej linii zawsze wynosi 0.

Następnie $q$ linii, z których każda zawiera ciąg znaków $s$ o długości $n$, reprezentujący zapis jednego testu.

Wyjście

Wypisz $q$ linii, z których każda zawiera nieujemną liczbę całkowitą oznaczającą liczbę istotnie różnych sposobów przypisania wszystkich węzłów do dwóch głównych modułów dla danego testu, modulo $10^9 + 7$.

Przykład

Wejście 1

3 2
010
100
000
1?0
010

Wyjście 1

4
0

Uwagi

Dla pierwszego testu istnieją następujące cztery sposoby przypisania: 1. Przypisanie wszystkich węzłów do pierwszego głównego modułu; 2. Przypisanie wszystkich węzłów do drugiego głównego modułu; 3. Przypisanie węzłów 1 i 2 do pierwszego głównego modułu, a węzła 3 do drugiego głównego modułu; 4. Przypisanie węzłów 1 i 2 do drugiego głównego modułu, a węzła 3 do pierwszego głównego modułu.

Wejście 2

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

Wyjście 2

0
64
16
32
0