#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"; }