Электросеть состоит из $n$ узлов, соединенных между собой несколькими двунаправленными линиями электропередачи, образуя неориентированный граф.

При настройке сети все узлы распределяются по двум независимым основным модулям питания. Для узла $i$ ($1 \le i \le n$) определим количество его соседей в том же модуле $d_i$ как количество узлов, соединенных с узлом $i$ прямой линией и подключенных к тому же модулю питания, что и узел $i$.

Маленький S нашел записи о $q$ тестах, где каждый тест представлен строкой $s$ длины $n$. Для $i$-го узла ($1 \le i \le n$): Если $s_i = 0$, то требуется, чтобы в данной конфигурации количество соседей узла $i$ в том же модуле $d_i$ было четным; Если $s_i = 1$, то требуется, чтобы в данной конфигурации количество соседей узла $i$ в том же модуле $d_i$ было нечетным; * Если $s_i = ?$, то узел $i$ не участвует в записи, то есть к четности количества соседей узла $i$ в том же модуле требований нет.

Маленький T отметил, что множества узлов, участвующих в записях, обладают регулярной структурой вложенности. Конкретнее, пусть $S_i$ — множество узлов, участвующих в $i$-м тесте ($1 \le i \le q$) (то есть множество всех позиций в строке, отличных от $?$). Тогда для любых двух различных записей $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$ строк, каждая из которых содержит строку из $0$ и $1$ длиной $n$. В $i$-й строке ($1 \le i \le n$) $j$-й символ ($1 \le j \le n$) указывает, существует ли линия электропередачи между узлом $i$ и узлом $j$: $1$ — если существует, $0$ — в противном случае. Гарантируется отсутствие петель, то есть $i$-й символ в $i$-й строке всегда равен $0$.

Далее следуют $q$ строк, каждая из которых содержит строку $s$ длиной $n$, представляющую запись одного теста.

Выходные данные

Выведите $q$ строк, каждая из которых содержит неотрицательное целое число — количество существенно различных способов подключения всех узлов к двум основным модулям для соответствующего теста по модулю $10^9 + 7$.

Примеры

Входные данные 1

3 2
010
100
000
1?0
010

Выходные данные 1

4
0

Примечание

Для первого теста существует четыре способа подключения: 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

Примечание

Для второго теста (строка ??????) существует 64 способа подключения, так как нет никаких ограничений на четность соседей, и каждый из 6 узлов может быть подключен к одному из двух модулей ($2^6 = 64$). Для остальных тестов количество способов определяется наложенными ограничениями на четность.