#include <bits/stdc++.h>
using namespace std;
const int Nmax = 20;
int n, q;
int a[1 << Nmax], f[1 << Nmax], f0[1 << Nmax];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
string s;
cin >> s;
int lim = 1 << n;
for (int i = 0; i < lim; i++)
a[i] = f[i] = f0[i] = s[i] - '0';
// DP SOS
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < lim; mask++) {
if (mask & (1 << i)) f[mask] += f[mask ^ (1 << i)];
else f0[mask] += f0[mask ^ (1 << i)];
}
}
while (q--) {
cin >> s;
reverse(s.begin(), s.end()); // bit 0 = LSB
int one = 0, zero = 0, ques = 0;
for (int i = 0; i < n; i++) {
int bit = 1 << i;
if (s[i] == '1') one |= bit;
else if (s[i] == '0') zero |= bit;
else ques |= bit;
}
int ans = 0;
if (__builtin_popcount(ques) <= 6) {
// trực tiếp lặp submask
for (int sub = ques;; sub = (sub - 1) & ques) {
ans += a[sub | one];
if (sub == 0) break;
}
}
else if (__builtin_popcount(one) <= 6) {
// Inclusion-Exclusion trên mask one
ans = f[ques] * (__builtin_parity(one) ? -1 : 1);
for (int sub = one; sub; sub = (sub - 1) & one) {
if (__builtin_parity(sub) ^ __builtin_parity(one)) ans -= f[sub | ques];
else ans += f[sub | ques];
}
}
else if (__builtin_popcount(zero) <= 6) {
// Inclusion-Exclusion trên mask zero (SuperSOS)
ans = f0[one];
for (int sub = zero; sub; sub = (sub - 1) & zero) {
if (__builtin_parity(sub)) ans -= f0[sub | one];
else ans += f0[sub | one];
}
}
cout << ans << '\n';
}
return 0;
}
