#include<bits/stdc++.h>
using namespace std;
const int MAXN=1048576;
int dp[MAXN],ans[MAXN],pos[MAXN],pw[36],mask[MAXN],mask2[MAXN];
string Q[MAXN];
void compute(int n,string s)
{
int cnt=0;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*3;
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+1;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;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
string s;
cin>>n>>q>>s;
int z=min(8,n);
for(int i=1;i<=q;i++)
{
cin>>Q[i];
for(int j=0;j<z;j++) mask[i]=mask[i]*4+(Q[i][j]!='0')*2+(Q[i][j]!='1');
for(int j=z;j<n;j++) mask2[i]=mask2[i]*3+(Q[i][j]=='?')*2+(Q[i][j]=='1');
}
for(int i=0;i<(1<<z);i++)
{
int l=(i<<(n-z)),r=((i+1)<<(n-z))-1,val=0;
for(int j=z-1;j+1;j--) val=val*4+(1<<((i>>j)%2));
string t;
for(int j=l;j<=r;j++) t+=s[j];
compute(n-z,t);
for(int j=1;j<=q;j++) if((mask[j]&val)==val) ans[j]+=dp[mask2[j]];
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
