#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 = 3;
int ans[MAX_Q];
int dp[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;
for (int i = 0; i < k; ++i) {
if (t[i] == '?') {
mask |= 1 << i;
} else if (t[i] == '1') {
shift |= 1 << i;
}
}
shifts[shift].emplace_back(mask, j);
}
for (const auto& [shift, values] : shifts) {
if (values.size() >= MAGIC) {
int total_mask = ((1 << k) - 1) & (~shift);
dp[0] = s[shift] - '0';
for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
dp[mask] = s[mask | shift] - '0';
}
for (int bit = 0; bit < k; ++bit) {
if (shift & (1 << bit)) continue;
for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
if (mask & (1 << bit)) {
dp[mask] += dp[mask ^ (1 << bit)];
}
}
}
for (const auto& [mask, idx] : values) {
ans[idx] = dp[mask];
}
for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
dp[mask] = 0;
}
} else {
for (const auto& [mask, idx] : values) {
ans[idx] = s[shift] - '0';
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
ans[idx] += s[submask | shift] - '0';
}
}
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
/*
4
1
3141592653589793
?01?
*/
