Mạng lưới điện bao gồm $n$ nút, các nút được kết nối với nhau thông qua một số đường dây truyền tải hai chiều, tạo thành một đồ thị vô hướng.

Khi cấu hình mạng lưới, tất cả các nút sẽ được phân bổ vào hai mô-đun cung cấp điện chính độc lập. Đối với nút $i$ ($1 \le i \le n$), định nghĩa số nút láng giềng cùng mô-đun $d_i$ là: số lượng các nút được kết nối trực tiếp với nút $i$ và nằm trong cùng mô-đun cung cấp điện với nút $i$.

Tiểu S đã tìm thấy hồ sơ của $q$ lần kiểm tra, mỗi lần kiểm tra được biểu diễn bằng một chuỗi $s$ có độ dài $n$. Đối với nút thứ $i$ ($1 \le i \le n$): Nếu $s_i = 0$, yêu cầu trong cấu hình này, số nút láng giềng cùng mô-đun $d_i$ của nút $i$ phải là số chẵn; Nếu $s_i = 1$, yêu cầu trong cấu hình này, số nút láng giềng cùng mô-đun $d_i$ của nút $i$ phải là số lẻ; * Nếu $s_i = ?$, hồ sơ không đề cập đến nút $i$, nghĩa là không có yêu cầu về tính chẵn lẻ của số nút láng giềng cùng mô-đun đối với nút $i$.

Tiểu T chỉ ra rằng tập hợp các nút liên quan trong các hồ sơ có mối quan hệ lồng nhau quy củ. Cụ thể, gọi $S_i$ là tập hợp các nút liên quan trong lần kiểm tra thứ $i$ ($1 \le i \le q$) (tức là tập hợp các vị trí trong chuỗi tương ứng không phải là $?$), thì với bất kỳ hai hồ sơ kiểm tra khác nhau $i, j$ ($1 \le i < j \le q$), $S_i$ và $S_j$ chắc chắn thỏa mãn một trong ba mối quan hệ sau: $S_i \subseteq S_j$, $S_j \subseteq S_i$, hoặc $S_i \cap S_j = \emptyset$.

Để nhanh chóng cấu hình mạng lưới điện, bạn cần hỗ trợ Tiểu T và Tiểu S tính toán số lượng phương án khác nhau về bản chất để kết nối tất cả các nút vào hai mô-đun chính trong mỗi lần kiểm tra. Hai phương án được coi là khác nhau khi và chỉ khi tồn tại ít nhất một nút được kết nối vào các mô-đun chính khác nhau trong hai phương án. Vì kết quả có thể rất lớn, bạn chỉ cần đưa ra kết quả sau khi lấy mô-đun $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên dương $n, q$ ($1 \le n, q \le 3 \times 10^3$).

Tiếp theo là $n$ dòng, mỗi dòng chứa một chuỗi 01 có độ dài $n$, trong đó ký tự thứ $j$ ($1 \le j \le n$) của dòng thứ $i$ ($1 \le i \le n$) biểu thị sự tồn tại của đường dây truyền tải giữa nút $i$ và nút $j$. Nếu tồn tại thì là $1$, ngược lại là $0$. Đảm bảo không có đường dây truyền tải nào kết nối với chính nó, tức là ký tự thứ $i$ của dòng thứ $i$ ($1 \le i \le n$) luôn là $0$.

Tiếp theo là $q$ dòng, mỗi dòng chứa một chuỗi $s$ có độ dài $n$, biểu thị hồ sơ của một lần kiểm tra.

Dữ liệu ra

Xuất ra $q$ dòng, mỗi dòng một số nguyên không âm, biểu thị số lượng phương án khác nhau về bản chất để kết nối tất cả các nút vào hai mô-đun chính trong lần kiểm tra đó, kết quả lấy mô-đun $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

3 2
010
100
000
1?0
010

Dữ liệu ra 1

4
0

Ghi chú

Đối với lần kiểm tra đầu tiên, có bốn phương án kết nối sau: 1. Kết nối tất cả các nút vào mô-đun chính thứ nhất; 2. Kết nối tất cả các nút vào mô-đun chính thứ hai; 3. Kết nối nút 1, 2 vào mô-đun chính thứ nhất, nút 3 vào mô-đun chính thứ hai; 4. Kết nối nút 1, 2 vào mô-đun chính thứ hai, nút 3 vào mô-đun chính thứ nhất.

Dữ liệu vào 2

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

Dữ liệu ra 2

0
64
16
32
0