#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1 << 20;
int dp[maxn], pos[maxn], pw[36];
void compute(int n, string s){
for(int i = 0; i < pw[n]; i++) dp[i] = 0;
int cnt = 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';
pos[++cnt] = res;
}
for(int i = 0; i < n; i++){
int pcnt = cnt;
for(int j = 1, v = pos[j]; j <= pcnt; v = pos[++j]){
if((v / pw[i]) % 3 == 0){
dp[v + pw[i] * 2] = dp[v] + dp[v + pw[i]];
pos[++cnt] = v + pw[i] * 2;
}
}
}
}
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(8ll, 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)); //val là mask đại diện cho phần đầu
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";
}
