#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=(1<<20)+5;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int l,q,n,dp[maxn],dp1[maxn],f[maxn],ans;
string ss,s;
vector<int> L;
void solve0()
{
reverse(s.begin(),s.end());
L.clear();
int ori=0;
for1(i,0,s.size()-1)
{
if (s[i]=='0') L.pb(i);
if (s[i]=='1') ori+=(1<<i);
}
int g=L.size(),ori2;
ans=0;
for1(mask1,0,(1<<g)-1)
{
ori2=ori;
for1(j,0,g-1)
{
if ((mask1>>j)&1) ori2+=(1<<L[j]);
}
if (__builtin_popcount(mask1)%2==0)
{
//cerr<< ori2<<'\n';
ans+=dp1[ori2];
}
else ans-=dp1[ori2];
}
cout << ans<<'\n';
}
void solve1()
{
reverse(s.begin(),s.end());
L.clear();
int ori=0;
for1(i,0,s.size()-1)
{
if (s[i]=='1') L.pb(i);
if (s[i]=='1' || s[i]=='?') ori+=(1<<i);
}
int g=L.size(),ori2;
ans=0;
for1(mask1,0,(1<<g)-1)
{
ori2=ori;
for1(j,0,g-1)
{
if ((mask1>>j)&1) ori2^=(1<<L[j]);
}
if (__builtin_popcount(mask1)%2==0)
{
//cerr<< ori2<<'\n';
ans+=dp[ori2];
}
else ans-=dp[ori2];
}
cout << ans<<'\n';
}
void solve()
{
reverse(s.begin(),s.end());
L.clear();
int ori=0;
for1(i,0,s.size()-1)
{
if (s[i]=='?') L.pb(i);
if (s[i]=='1') ori+=(1<<i);
}
int g=L.size(),ori2;
ans=0;
for1(mask1,0,(1<<g)-1)
{
ori2=ori;
for1(j,0,g-1)
{
if ((mask1>>j)&1) ori2+=(1<<L[j]);
}
ans+=f[ori2];
}
cout << ans<<'\n';
}
void sol()
{
cin >> l>> q>>ss;
n=1LL<<l;
for1(i,0,n-1)
{
f[i]=dp[i]=dp1[i]=(ss[i]-'0');
}
for1(i,0,l-1)
{
for1(mask,0,n-1)
{
if ((mask>>i)&1)
{
dp[mask]+=dp[mask^(1<<i)];
}
else
{
dp1[mask]+=dp1[mask^(1<<i)];
}
}
}
/*
dp la tong mask con
dp1 la tong mask cha
*/
// cout << dp1[3];
while (q--)
{
cin >> s;
int cnt1=0,cnt0=0;
for1(i,0,s.size()-1)
{
if (s[i]=='0') cnt0++;
if (s[i]=='1') cnt1++;
}
if (cnt1<7)
{
solve1();
}
else if (cnt0<7)
{
solve0();
}
else
{
solve();
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("GROUPDIV.inp","r",stdin);
// freopen("GROUPDIV.out","w",stdout);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
3 1
12345678
?11
*/
