#pragma GCC optimize("Ofast")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
int x, q;
std::string str;
int dp_subsets[1<<20];
int dp_supersets[1<<20];
void precalc_dp() {
for (int i = 0; i < (1<<x); i++) {
dp_subsets[i] = str[i] - '0';
}
for (int i = 0; i < x; i++) {
for (int mask = 0; mask < (1<<x); mask++) {
if (mask&(1<<i)) {
dp_subsets[mask] += dp_subsets[mask^(1<<i)];
}
}
}
for (int i = 0; i < (1<<x); i++) {
dp_supersets[i] = str[i] - '0';
}
for (int i = 0; i < x; i++) {
for (int mask = (1<<x)-1; mask >= 0; mask--) {
if (!(mask&(1<<i))) {
dp_supersets[mask] += dp_supersets[mask^(1<<i)];
}
}
}
}
int to_decimal(const std::string& str) {
int ret = 0;
for (int i = 0; i < str.size(); i++) {
ret <<= 1;
ret += (str[i]=='1');
}
return ret;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> q;
std::cin >> str;
precalc_dp();
/*for (int i = 0; i < (1<<x); i++) {
std::cout << i << " " << dp_subsets[i] << " " << dp_supersets[i] << "\n";
}*/
while (q--) {
std::string pattern;
std::cin >> pattern;
std::vector<int> aps[3];
for (int i = 0; i < x; i++) {
if (pattern[i] == '0' || pattern[i] == '1') {
aps[pattern[i]-'0'].emplace_back(i);
}
else {
aps[2].emplace_back(i);
}
}
// min_cnt <= 6
int min_cnt = std::min({aps[0].size(), aps[1].size(), aps[2].size()});
if (aps[2].size() == min_cnt) {
int ret = 0;
for (int mask = 0; mask < (1<<aps[2].size()); mask++) {
for (int i = 0; i < aps[2].size(); i++) {
pattern[aps[2][i]] = ((mask>>i)&1) + '0';
}
ret += str[to_decimal(pattern)]-'0';
}
std::cout << ret << "\n";
}
else if (aps[0].size() == min_cnt) {
int ret = 0;
int one_mask = 0;
for (int i = 0; i < aps[1].size(); i++) {
one_mask |= (1<<(x-aps[1][i]-1));
}
for (int mask = 0; mask < (1<<aps[0].size()); mask++) {
int full_mask = one_mask;
for (int i = 0; i < aps[0].size(); i++) {
if (mask&(1<<i)) {
full_mask |= (1<<(x-aps[0][i]-1));
}
}
int sgn = ((__builtin_popcount(mask))&1) ? -1 : 1;
ret += sgn * dp_supersets[full_mask];
}
std::cout << ret << "\n";
}
else {
int ret = 0;
int question_mask = 0;
for (int i = 0; i < aps[2].size(); i++) {
question_mask |= (1<<(x-aps[2][i]-1));
}
for (int mask = 0; mask < (1<<aps[1].size()); mask++) {
int full_mask = question_mask;
for (int i = 0; i < aps[1].size(); i++) {
if (mask&(1<<i)) {
full_mask |= (1<<(x-aps[1][i]-1));
}
}
int sgn = ((aps[1].size()-__builtin_popcount(mask))&1) ? -1 : 1;
ret += sgn * dp_subsets[full_mask];
}
std::cout << ret << "\n";
}
}
}
