#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
constexpr int MAX_Q = 1e6 + 5;
constexpr int MAX_BIT = 20;
constexpr int MAX_N = 1 << 20;
constexpr int MAGIC = 12;
int ans[MAX_Q];
int dp[MAX_N];
int max_mask[MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k, q;
cin >> k >> q;
string s;
cin >> s;
map<int, vector<pair<int, int>>> shifts;
for (int j = 0; j < q; ++j) {
string t;
cin >> t;
reverse(t.begin(), t.end());
int mask = 0;
int shift = 0;
int bits_cnt = 0;
for (int i = 0; i < k; ++i) {
if (t[i] == '?') {
mask |= 1 << i;
++bits_cnt;
} else if (t[i] == '1') {
shift |= 1 << i;
}
}
if (bits_cnt <= MAGIC) {
int res = s[shift] - '0';
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
res += s[submask + shift] - '0';
}
ans[j] = res;
} else {
shifts[shift].emplace_back(mask, j);
max_mask[shift] = max(max_mask[shift], __lg(mask) + 1);
}
}
for (const auto& [shift, values] : shifts) {
int n = 1 << max_mask[shift];
for (int mask = 0; (mask | shift) < n; ++mask) {
if ((mask & shift) == 0) {
dp[mask] = s[mask | shift] - '0';
}
}
for (int bit = 0; bit < k; ++bit) {
if (shift & (1 << bit)) continue;
for (int mask = 0; (mask | shift) < n; ++mask) {
if ((mask & shift) != 0) continue;
if (mask & (1 << bit)) {
dp[mask] += dp[mask ^ (1 << bit)];
}
}
}
for (const auto& [mask, idx] : values) {
ans[idx] = dp[mask];
}
for (int mask = 0; (mask | shift) < n; ++mask) {
dp[mask] = 0;
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
/*
4
1
3141592653589793
?01?
*/
