#include <algorithm>
#include <iostream>
using namespace std;
const int N = 20;
const int Q = 1000000;
const int M = 6;
const int P = 4782969;
char aa[(1 << N) + 1], cc[Q][N + 1];
int bb[Q], ss[P], ans[Q];
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++)
p_ *= 3;
for (int h = 0; h < q; h++) {
cin >> cc[h], reverse(cc[h], cc[h] + n);
for (int i = n - 1; i >= m; i--)
bb[h] = bb[h] * 3 + (cc[h][i] != '?' ? cc[h][i] - '0' : 2);
}
for (int a = 0; a < 1 << m; a++) {
for (int b = 0; b < p_; b++) {
int i = m, p = 1;
while (i < n && b / p % 3 != 2)
i++, p *= 3;
if (i == n) {
int a_ = a;
for (i = m, p = 1; i < n; i++, p *= 3)
a_ ^= b / p % 3 << i;
ss[b] = aa[a_] - '0';
} else
ss[b] = ss[b - p * 2] + ss[b - p];
}
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;
}
