#include <bits/stdc++.h>
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
string s; cin >> s;
for ( auto &v: s ) v -= '0';
vector <int> pw(n + 1, 1);
for ( int i = 1; i <= n; i++ ){
pw[i] = pw[i - 1] * 3;
}
vector <string> qu(q);
for ( auto &u: qu ) cin >> u;
if ( n <= 7 ){
for ( auto &u: qu ){
int cnt = 0;
for ( int mask = 0; mask < (1 << n); mask++ ){
bool bad = false;
int rev = 0;
for ( int i = 0; i < n; i++ ){
rev = rev * 2 + (mask >> i & 1);
if ( u[i] != '?' && (mask >> i & 1) != u[i] - '0' ) bad = 1;
}
cnt += !bad * s[rev];
}
cout << cnt << '\n';
}
return 0;
}
int m = n - 7;
vector <int> ans(q);
for ( int lf = 0; lf < 128; lf++ ){
vector <int> dp(pw[m]);
for ( int mask = 0; mask < pw[m]; mask++ ){
bool has_q = false;
for ( int i = 0; i < m; i++ ){
int b = mask / pw[i] % 3;
if ( b == 2 ){
dp[mask] = dp[mask - pw[i]] + dp[mask - pw[i] * 2];
has_q = 1; break;
}
}
if ( !has_q ){
int x = 0;
for ( int i = 0; i < m; i++ ){
x = x * 2 + mask / pw[i] % 3;
}
for ( int i = 0; i < 7; i++ ) x = x * 2 + (lf >> i & 1);
dp[mask] = s[x];
}
}
for ( int i = 0; i < q; i++ ){
bool bad = false;
string &t = qu[i];
for ( int j = n - 1; j >= n - 7; j-- ){
if ( t[j] != '?' && (lf >> j & 1) != t[j] - '0' ) bad = 1;
}
if ( bad ) continue;
int x = 0;
for ( int j = 0; j < m; j++ ){
x = x + pw[j] * (t[j] == '?' ? 2 : t[j] - '0');
}
ans[i] += dp[x];
}
}
for ( auto &x: ans ) cout << x << '\n';
}
