#include <bits/stdc++.h>
using namespace std;
const int maxn = 21;
const int maxsz = 1<<21;
int x[maxsz];
int sos[maxsz];
int soo[maxsz];
int dp[maxn][maxsz];
int recq(int sv,int tpos,vector<int>& posq)
{
if(tpos == posq.size())
{
return x[sv];
}
else
{
return recq(sv,tpos+1,posq) + recq(sv+(1<<posq[tpos]),tpos+1,posq);
}
}
int rec0(int sv,int c0,int tpos,vector<int>& posq)
{
if(tpos == posq.size())
{
return (c0%2 == 0 ? 1 : -1)*sos[sv];
}
else
{
return rec0(sv,c0+1,tpos+1,posq) + rec0(sv+(1<<posq[tpos]),c0,tpos+1,posq);
}
}
int rec1(int sv,int c1,int tpos,vector<int>& posq)
{
if(tpos == posq.size())
{
return (c1%2 == 0 ? 1 : -1)*soo[sv];
}
else
{
return rec1(sv,c1,tpos+1,posq) + rec1(sv+(1<<posq[tpos]),c1+1,tpos+1,posq);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,q;
cin >> n >> q;
int sz = 1<<n;
for(int j = 0;j < sz;++j)
{
char c;
cin >> c;
x[j] = c-'0';
}
for(int i = 0;i <= n;++i)
{
for(int j = 0;j < sz;++j)
{
if(i == 0)
{
dp[i][j] = x[j];
}
else
{
dp[i][j] = ((j&(1<<(i-1))) == 0 ? dp[i-1][j] : dp[i-1][j] + dp[i-1][j^(1<<(i-1))]);
}
}
}
for(int i = 0;i < sz;++i)
{
sos[i] = dp[n][i];
}
for(int i = 0;i <= n;++i)
{
for(int j = 0;j < sz;++j)
{
if(i == 0)
{
dp[i][j] = x[j];
}
else
{
dp[i][j] = ((j&(1<<(i-1))) != 0 ? dp[i-1][j] : dp[i-1][j] + dp[i-1][j^(1<<(i-1))]);
}
}
}
for(int i = 0;i < sz;++i)
{
soo[i] = dp[n][i];
}
while(q--)
{
vector<char> c(n);
int c0 = 0,c1 = 0,cq = 0;
for(int j = 0;j < n;++j)
{
cin >> c[j];
if(c[j] == '?')
cq++;
else if(c[j] == '0')
c0++;
else
c1++;
}
if(cq <= 6)
{
int sv = 0;
vector<int> posq;
for(int j = 0;j < n;++j)
{
if(c[j] == '?')
posq.push_back(n-j-1);
sv*=2;
sv += (c[j] == '1' ? 1 : 0);
}
cout << recq(sv,0,posq) << "\n";
}
else if(c0 <= 6)
{
int sv = 0;
vector<int> pos0;
for(int j = 0;j < n;++j)
{
if(c[j] == '0')
pos0.push_back(n-j-1);
sv*=2;
sv += (c[j] == '1' ? 1 : 0);
}
cout << rec1(sv,0,0,pos0) << "\n";
}
else
{
int sv = 0;
vector<int> pos1;
for(int j = 0;j < n;++j)
{
if(c[j] == '1')
pos1.push_back(n-j-1);
sv*=2;
sv += (c[j] == '?' ? 1 : 0);
}
cout << rec0(sv,0,0,pos1) << "\n";
}
}
}
