#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (1 << 20) + 10;
ll l, q, dp1[MAXN], dp2[MAXN];
string s, t;
void input() {
cin >> l >> q >> s;
}
void calcDp() {
for (int i = 0; i < (1 << l); i++) {
dp1[i] = (s[i] - '0');
dp2[(1 << l) - 1 - i] = (s[i] - '0');
}
for (int i = 0; i < l; i++)
for (int j = 0; j < (1 << l); j++) {
dp1[j] += (((j >> i) & 1)? dp1[j - (1 << i)]: 0);
dp2[j] += (((j >> i) & 1)? dp2[j - (1 << i)]: 0);
}
}
ll find1(int i, int cnt, int num) {
if (i == l)
return (cnt % 2 == 0? dp1[num]: -dp1[num]);
if (t[i] == '?')
return find1(i + 1, cnt, num * 2 + 1);
if (t[i] == '0')
return find1(i + 1, cnt, num * 2);
return find1(i + 1, cnt + 1, num * 2) + find1(i + 1, cnt, num * 2 + 1);
}
ll find2(int i, int cnt, int num) {
if (i == l)
return (cnt % 2 == 0? dp2[num]: -dp2[num]);
if (t[i] == '?')
return find2(i + 1, cnt, num * 2 + 1);
if (t[i] == '1')
return find2(i + 1, cnt, num * 2);
return find2(i + 1, cnt + 1, num * 2) + find2(i + 1, cnt, num * 2 + 1);
}
ll find3(int i, int num) {
if (i == l)
return (s[num] - '0');
if (t[i] == '0')
return find3(i + 1, 2 * num);
if (t[i] == '1')
return find3(i + 1, 2 * num + 1);
return find3(i + 1, 2 * num) + find3(i + 1, 2 * num + 1);
}
ll findAns() {
int cnt1 = 0, cnt0 = 0;
for (int i = 0; i < l; i++) {
if (t[i] == '1')
cnt1++;
else if (t[i] == '0')
cnt0++;
}
if (cnt1 <= cnt0 && cnt1 <= (l - cnt1 - cnt0))
return find1(0, 0, 0);
if (cnt0 <= cnt1 && cnt0 <= (l - cnt1 - cnt0))
return find2(0, 0, 0);
return find3(0, 0);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
input();
calcDp();
for (int i = 0; i < q; i++) {
cin >> t;
cout << findAns() << '\n';
}
return 0;
}
