//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
const int nmax = 4e5 + 5, N = 1e5;
const ll oo = 1e9;
const int lg = 31, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;
int L, q;
string s;
int F[1 << 20], G[1 << 20], cnt[1 << 20];
int bit(int msk, int x){
return msk>> x & 1;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
cin >> L >> q;
cin >> s;
for(int i = 0; i < (1 << L) ; ++i){
int c1 = 0, c2 = 0;
for(int k = 1; k <= L; ++k){
if(bit(i, L - k)){
c1 += (1 << (k - 1));
}
else c2 += (1 << (k - 1));
}
cnt[c1] += s[i] - '0';
F[c1] += s[i] - '0';
G[c2] += s[i] - '0';
}
for(int i = 0; i < L; ++i){
for(int msk = 0; msk < (1 << L); ++msk){
if(!bit(msk, i)){
F[msk ^ (1 << i)] += F[msk];
G[msk ^ (1 << i)] += G[msk];
}
}
}
string tmp;
vector<int> c0, c1, c2;
while(q--){
cin >> tmp;
c0.clear(); c1.clear();c2.clear();
for(int i = 0; i < L; ++i){
char x = tmp[i];
if(x == '0'){
c0.push_back(i);
}
else if(x == '1'){
c1.push_back(i);
}
else c2.push_back(i);
}
if((int)c1.size() <= 6){
// cout << "%";
int res = 0;
for(auto p : c1) res += (1 << p);
for(auto p : c2) res += (1 << p);
ll ans = 0;
for(int msk = 0; msk < (1 << c1.size()); ++msk){
int cur = res;
for(int i = 0; i < c1.size(); ++i){
if(bit(msk, i)){
cur ^= (1 << c1[i]);
}
}
int s = __builtin_popcount(msk);
if(s & 1) ans -= F[cur];
else ans += F[cur];
}
cout << ans << endl;
}
else if((int)c0.size() <= 6){
// cout << "?";
int res = 0;
for(auto p : c0) res += (1 << p);
for(auto p : c2) res += (1 << p);
ll ans = 0;
for(int msk = 0; msk < (1 << c0.size()); ++msk){
int cur = res;
for(int i = 0; i < c0.size(); ++i){
if(bit(msk, i)){
cur ^= (1 << c0[i]);
}
}
int s = __builtin_popcount(msk);
if(s & 1) ans -= G[cur];
else ans += G[cur];
}
cout << ans << endl;
}
else{
// cout << "#";
int res = 0;
for(auto p : c1) res += (1 << p);
int ans = 0;
for(int msk = 0; msk < (1 << c2.size()); ++msk){
int cur = res;
for(int i = 0; i < c2.size(); ++i){
if(bit(msk, i)){
cur ^= (1 << c2[i]);
}
}
ans += cnt[cur];
}
cout << ans << endl;
}
}
}
/*
3 5
12345678
000
0??
1?0
?11
???
3 1
12345678
???
*/
