#include <algorithm>
#include <iostream>
using namespace std;
const int N = 20;
const int Q = 1000000;
const int M = 7;
const int P = 4782969;
char aa[(1 << N) + 1], tt[N + 1], cc[Q][M];
int pp[N], bb[Q], ans[Q], ii[P], ss[P];
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int n, q; cin >> n >> q >> aa;
int m = min(M, n), p_ = 1;
for (int i = m; i < n; i++)
pp[i] = p_, p_ *= 3;
for (int h = 0; h < q; h++) {
cin >> tt, reverse(tt, tt + n);
for (int i = 0; i < n; i++)
if (i < m)
cc[h][i] = tt[i];
else
bb[h] += (tt[i] != '?' ? tt[i] - '0' : 2) * pp[i];
}
for (int b = 0; b < p_; b++) {
int i = m;
while (i < n && b / pp[i] % 3 != 2)
i++;
if (i < n) {
ii[b] = i;
continue;
}
int a = 0;
for (i = m; i < n; i++)
a ^= b / pp[i] % 3 << i;
ii[b] = -a;
}
for (int a = 0; a < 1 << m; a++) {
for (int b = 0; b < p_; b++) {
int i = ii[b];
ss[b] = i > 0 ? ss[b - pp[i] * 2] + ss[b - pp[i]] : aa[-i ^ a] - '0';
}
for (int h = 0; h < q; h++) {
bool yes = true;
for (int i = 0; i < m; i++)
if (cc[h][i] != '?' && cc[h][i] - '0' != (a >> i & 1)) {
yes = false;
break;
}
if (yes)
ans[h] += ss[bb[h]];
}
}
for (int h = 0; h < q; h++)
cout << ans[h] << '\n';
return 0;
}
