#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
#define BLOK 13
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,q;
const int N=(1<<20)+5;
const int M=1594330;
int arr[N];
int dp[M],pw[22],ans[N];
char s[N],t[22];
vector<PII>adj[22];
bitset<N>ok[130];
int link[N];
int two[M];
bitset<M>vis;
void rec(int pos,int mask,int bit,int last){
if(pos==min(n,BLOK)){
adj[bit].pb(mp(mask,last));
return;
}
rec(pos+1,mask*3,bit,last);
rec(pos+1,mask*3+1,bit,last);
rec(pos+1,mask*3+2,bit+1,min(n,BLOK)-pos-1);
}
//~ int two(int x){
//~ int bit=0,res=0;
//~ while(x>=1){
//~ assert(x%3<2);
//~ if(x%3)
//~ res+=(1<<bit);
//~ x/=3;bit++;
//~ }
//~ return res;
//~ }
void f(int l,int r,int mask,int ind){
if(l==r){
ok[mask][ind]=1;
//~ query[mask].pb(mp(suf,ind));
return;
}
if(t[l]=='0')
f(l+1,r,mask*2,ind);
if(t[l]=='1')
f(l+1,r,mask*2+1,ind);
if(t[l]=='?'){
f(l+1,r,mask*2,ind);
f(l+1,r,mask*2+1,ind);
}
}
void pre(int pos,int uc,int iki){
if(pos==13){
two[uc]=iki;
return;
}
for(int i=0;i<3;i++)
pre(pos+1,uc*3+i,iki*2+i);
}
int main(){
//~ freopen("file.in", "r", stdin);
pre(0,0,0);
scanf("%d%d",&n,&q);
scanf("%s",s);
pw[0]=1;
for(int i=1;i<=BLOK;i++)
pw[i]=pw[i-1]*3;
if(n<=BLOK){
rec(0,0,0,-1);
tr(it,adj[0])
dp[it->ff]=s[two[it->ff]]-'0';
for(int j=1;j<=n;j++)
tr(it,adj[j])
dp[it->ff]=dp[it->ff-pw[it->ss]]+dp[it->ff-2*pw[it->ss]];
for(int i=1;i<=q;i++){
scanf("%s",t);
int base=0;
for(int j=0;j<n;j++){
base=base*3;
if(t[j]=='1')
base++;
if(t[j]=='?')
base+=2;
}
printf("%d\n",dp[base]);
}
}
else{
rec(0,0,0,-1);
for(int i=1;i<=q;i++){
scanf("%s",t);
int tmp=0;
for(int j=0;j<n;j++){
tmp*=3;
if(t[j]=='1')
tmp++;
if(t[j]=='?')
tmp+=2;
}
if(vis[tmp]){
link[i]=vis[tmp];
continue;
}
vis[tmp]=1;
int base=0;
for(int j=n-BLOK;j<n;j++){
base=base*3;
if(t[j]=='1')
base++;
if(t[j]=='?')
base+=2;
}
f(0,n-BLOK,0,i);arr[i]=base;
}
int lek=(1<<BLOK);
for(int mask=0;mask<(1<<(n-BLOK));mask++){
tr(it,adj[0])
dp[it->ff]=s[lek*mask+two[it->ff]]-'0';
for(int i=1;i<=BLOK;i++)
tr(it,adj[i])
dp[it->ff]=dp[it->ff-pw[it->ss]]+dp[it->ff-2*pw[it->ss]];
for(int i=1;i<=q;i++)
if(!link[i] and ok[mask][i])
ans[i]+=dp[arr[i]];
}
for(int i=1;i<=q;i++){
if(!link[i])
printf("%d\n",ans[i]);
else
printf("%d\n",ans[link[i]]);
}
}
return 0;
}
