#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e6+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll dp[N],l,po[N],q,k,ans[N];
string s,a;
vector<pll> que[(1<<12)];
ll get3(ll val,ll ip){
return (val/po[ip])%3;
}
void cal(ll id){
memset(dp,0,sizeof(dp));
REP(i,po[k]){
ll tx=0,ck=1;
REP(j,k){
if(get3(i,k-j-1)==2){
dp[i]=dp[i-2*po[k-j-1]]+dp[i-po[k-j-1]];
ck=0;
break;
}
tx=tx*2+get3(i,k-j-1);
}
if(ck)dp[i]=s[(id<<k)+tx]-'0';
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>l>>q>>s;
k=min(l-1,10LL);
po[0]=1;
REP1(i,k)po[i]=po[i-1]*3;
REP(T,q){
cin>>a;
ll tx=0;
for(int i=l-k;i<l;i++)tx=tx*3+(a[i]=='?'?2:a[i]-'0');
REP(i,(1<<(l-k))){
bool ck=1;
REP(j,l-k){
if(a[j]=='?')continue;
if((a[j]-'0')!=(i>>(l-k-j-1))){ck=0;break;}
}
if(ck){
que[i].pb(mp(tx,T));
}
}
}
REP(i,(1<<(l-k))){
cal(i);
for(auto j:que[i]){
ans[j.Y]+=dp[j.X];
}
}
REP(i,q)cout<<ans[i]<<"\n";
return 0;
}
