#include<bits/stdc++.h>
using namespace std;
const int maxn = 1 << 20;
int dp[maxn], pw[36];
void compute(int n, string s){
for(int i = 0; i < pw[n]; i++) dp[i] = 0;
for(int i = 0; i < (1 << n); i++){
int res = 0;
for(int j = n - 1; j >= 0; j--) res = res * 3 + (i >> j) % 2;
dp[res] = s[i] - '0';
}
for(int i = 0; i < n; i++){
for(int mask = 0; mask < pw[n]; mask++) if((mask / pw[i]) % 3 == 0) dp[mask + 2 * pw[i]] = dp[mask] + dp[mask + pw[i]];
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
string s; cin >> s;
int cut = min(8, n);
vector<int> mask1(q + 1), mask2(q + 1), ans(q + 1);
for(int i = 1; i <= q; i++){
string t; cin >> t;
for(int j = 0; j < cut; j++) mask1[i] = 4 * mask1[i] + 2 * (t[j] != '0') + (t[j] != '1');
for(int j = cut; j < n; j++) mask2[i] = 3 * mask2[i] + 2 * (t[j] == '?') + (t[j] == '1');
}
pw[0] = 1;
for(int i = 1; i <= 22; i++) pw[i] = pw[i - 1] * 3;
for(int i = 0; i < (1 << cut); i++){
int l = (i << (n - cut)), r = l + (1 << (n - cut)) - 1, val = 0;
for(int j = cut - 1; j >= 0; j--) val = val * 4 + (1 << ((i >> j) % 2));
string t;
for(int j = l; j <= r; j++) t += s[j];
compute(n - cut, t);
for(int j = 1; j <= q; j++) if((mask1[j] & val) == val) ans[j] += dp[mask2[j]];
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
