#include <bits/stdc++.h>
using namespace std;
#define MAXN 1594323
int len, q;
int dp[MAXN];
string s;
int ans[MAXN];
int pw[21];
int lowbit[MAXN];
int mp[MAXN];
int counter;
bool isSub[2187][128];
int p1[MAXN], p2[MAXN];
int main(){
// freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> len >> q >> s;
for(int i = 0; i<2187; i++){
for(int j = 0; j<128; j++){
isSub[i][j] = 1;
int c1 = i, c2 = j;
for(int k = 0; k < 7; k++){
if((c1%3 != 2 && c2%2 != c1%3)) isSub[i][j] = 0;
c1 /= 3, c2 /= 2;
}
}
}
pw[0] = 1; for(int i = 1; i<=20; i++) pw[i] = pw[i-1]*3;
lowbit[0] = lowbit[1] = MAXN;
for(int i = 2; i<MAXN; i++){
if(i%3 == 2) lowbit[i] = 0;
else lowbit[i] = lowbit[i/3]+1;
}
for(int i = 0; i<MAXN; i++){
if(lowbit[i] >= MAXN) mp[counter++] = i;
}
for(int i = 0; i<q; i++){
string ss; cin >> ss;
reverse(ss.begin(), ss.end());
int cur2 = 0;
for(int j = 0; j<min(7, len); j++){
if(ss[j] == '?') cur2 += pw[j]*2;
else cur2 += pw[j]*(ss[j]-'0');
}
p2[i] = cur2;
int cur1 = 0;
for(int j = 7; j<len; j++){
if(ss[j] == '?') cur1 += pw[j-7]*2;
else cur1 += pw[j-7]*(ss[j]-'0');
}
p1[i] = cur1;
}
// for(int i = 0; i<100; i++) cout << lowbit[i] << " ";
// cout << endl;
for(int i = 0; i < min(128, (int)s.length()); i++){
memset(dp, 0, sizeof dp);
for(int j = 0, end = (1<<(max(len-7, 0))); j<end; j++) dp[mp[j]] = s[(j<<7)+i]-'0';
for(int j = 0; j<((len >= 7) ? pw[len-7] : 1); j++){
if(lowbit[j] < MAXN) dp[j] = dp[j-pw[lowbit[j]]]+dp[j-pw[lowbit[j]]*2];
}
for(int j = 0; j<q; j++){
if(isSub[p2[j]][i]) ans[j] += dp[p1[j]];
}
}
for(int i = 0; i<q; i++) cout << ans[i] << " ";
cout << endl;
}
