#include<bits/stdc++.h>
using namespace std;
int val[(1<<20)+5];
int dp[(1<<20)+5];
int dp2[(1<<20)+5];
int solve1(string s){
reverse(s.begin(),s.end());
vector<int>pos;
int temp=0;
for(int i=0;i<s.size();i++){
if(s[i]=='1')temp+=(1<<i);
else{
if(s[i]=='?')pos.push_back(i);
}
}
int ans=0;
if(pos.empty())return val[temp];
for(int i=0;i<(1<<pos.size());i++){
int sum=temp;
for(int j=0;j<pos.size();j++){
if((i>>j)&1)sum+=(1<<pos[j]);
}
ans+=val[sum];
}
return ans;
}
int solve2(string s){
reverse(s.begin(),s.end());
vector<int>pos;
int temp=0;
for(int i=0;i<s.size();i++){
if(s[i]=='1'){
temp+=(1<<i);
pos.push_back(i);
}
else{
if(s[i]=='?')temp+=(1<<i);
}
}
int ans=0;
if(pos.empty())return dp[temp];
for(int i=0;i<(1<<pos.size());i++){
int sum=temp;
for(int j=0;j<pos.size();j++){
if((i>>j)&1)sum^=(1<<pos[j]);
}
if(__builtin_popcount(i)%2==0)ans+=dp[sum];
else ans-=dp[sum];
}
return ans;
}
int solve3(string s){
reverse(s.begin(),s.end());
for(auto &x:s){
if(x=='0')x='1';
else if(x=='1')x='0';
}
vector<int>pos;
int temp=0;
for(int i=0;i<s.size();i++){
if(s[i]=='1'){
temp+=(1<<i);
pos.push_back(i);
}
else{
if(s[i]=='?')temp+=(1<<i);
}
}
int ans=0;
if(pos.empty())return dp2[temp];
for(int i=0;i<(1<<pos.size());i++){
int sum=temp;
for(int j=0;j<pos.size();j++){
if((i>>j)&1)sum^=(1<<pos[j]);
}
if(__builtin_popcount(i)%2==0)ans+=dp2[sum];
else ans-=dp2[sum];
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int l,q;cin>>l>>q;
string s;cin>>s;
for(int i=0;i<(1<<l);i++)val[i]=s[i]-'0',dp[i]=val[i];
for(int i=0;i<(1<<l);i++){
dp2[i^((1<<l)-1)]=val[i];
}
for(int j=0;j<l;j++)for(int i=0;i<(1<<l);i++)if((i>>j)&1)dp[i]+=dp[i^(1<<j)];
for(int j=0;j<l;j++)for(int i=0;i<(1<<l);i++)if((i>>j)&1)dp2[i]+=dp2[i^(1<<j)];
//for(int i=0;i<(1<<l);i++)cerr<<dp[i]<<"\n";
for(int i=0;i<q;i++){
string s;cin>>s;
int cnt[3]={0,0,0};
for(auto x:s){
if(x=='0')cnt[0]++;
else if(x=='1')cnt[1]++;
else cnt[2]++;
}
int mn=min({cnt[0],cnt[1],cnt[2]});
if(cnt[2]==mn){
cout<<solve1(s)<<"\n";
}else if(cnt[1]==mn){
cout<<solve2(s)<<"\n";
}else{
cout<<solve3(s)<<"\n";
}
}
}
