#include <bits/stdc++.h>
using namespace std;
// For clarity we use int for indices (since n is small) and ll for values that might be larger.
typedef long long ll;
// Fast bit–reversal for an n–bit number (assumes n <= 32)
inline int reverse_bits(int x, int n) {
int r = 0;
for (int i = 0; i < n; i++) {
r = (r << 1) | (x & 1);
x >>= 1;
}
return r;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
string toxic2;
cin >> toxic2;
// Precompute powers of 3.
vector<ll> three(25);
three[0] = 1;
for (int i = 1; i < 25; i++)
three[i] = three[i - 1] * 3;
// Reorder the toxic string using bit–reversal.
int totStates = 1 << n;
string toxic = toxic2;
for (int i = 0; i < totStates; i++) {
int newmask = reverse_bits(i, n);
toxic[i] = toxic2[newmask];
}
// m is the number of “prefix digits” (m <= 5)
int m = min(5, n - 1);
// dp is defined over states of length (n-m) digits (each digit in {0,1,2}).
int dpSize = three[n - m];
vector<int> dp(dpSize, 0);
// Precompute hh[]: for each binary mask of length (n-m), convert it into a base–3 number
// where a 0–bit gives a digit 1 and a 1–bit gives a digit 2.
int binarySize = 1 << (n - m);
vector<int> hh(binarySize, 0);
for (int i = 0; i < binarySize; i++){
int sum = 0;
for (int j = 0; j < n - m; j++){
if (i & (1 << j))
sum += 2 * three[j];
else
sum += three[j];
}
hh[i] = sum;
}
// Read query strings and compute a “mask” for each.
// In our construction, each query’s value is stored as
// mask = sum_{j=0}^{n-1} (digit * three[j])
// where digit is 1 for character '0' and 2 for character '1'.
vector<ll> mask(q, 0);
// Also precompute the lower m digits (low part) and the remaining high part.
vector<int> low(q, 0);
vector<int> high(q, 0);
for (int i = 0; i < q; i++){
string ss;
cin >> ss;
ll val = 0;
for (int j = 0; j < n; j++){
if (ss[j] == '0')
val += three[j];
else if (ss[j] == '1')
val += 2 * three[j];
}
mask[i] = val;
low[i] = val % three[m]; // lower m digits
high[i] = val / three[m]; // remaining digits
}
// Precompute a lookup table for the prefix condition.
// For each possible pref (a binary number with m bits) and each possible value x
// (the lower m digits, where x is in [0, three[m]) corresponding to m ternary digits),
// we require that:
// - if the i-th bit of pref is 0, then the i-th digit (base 3) is 0 or 1.
// - if the i-th bit of pref is 1, then the i-th digit is 0 or 2.
int prefSize = 1 << m;
int lowRange = three[m];
vector<vector<bool>> valid(prefSize, vector<bool>(lowRange, true));
for (int pref = 0; pref < prefSize; pref++){
for (int x = 0; x < lowRange; x++){
bool ok = true;
int temp = x;
for (int i = 0; i < m; i++){
int d = temp % 3;
temp /= 3;
if (d == 1 && (pref & (1 << i))) { ok = false; break; }
if (d == 2 && !(pref & (1 << i))) { ok = false; break; }
}
valid[pref][x] = ok;
}
}
vector<int> ans(q, 0);
// Outer loop over all possible prefixes.
// (There are only 2^m possibilities, at most 32.)
for (int pref = 0; pref < prefSize; pref++){
// Reset dp.
fill(dp.begin(), dp.end(), 0);
// Initialize dp:
// For each binary mask of length (n-m), we compute an index into our dp state
// via hh[] and set dp[state] = toxic[ index2 ] where:
// index2 = pref + (j * (1 << m))
// This corresponds to the way you rearranged toxic.
int binarySize2 = 1 << (n - m);
for (int j = 0; j < binarySize2; j++){
int state = hh[j];
int index2 = pref + j * (1 << m);
dp[state] = toxic[index2] - '0';
}
// --- DP transformation (“SOS DP in base 3”) ---
// Instead of the reverse j/while–loop, we iterate over every digit position.
// For each position i (0 <= i < n-m) and each state j, if the digit at position i is nonzero,
// add dp[j] to the dp state where that digit is decreased.
for (int i = 0; i < (n - m); i++){
for (int j = 0; j < dpSize; j++){
int d = (j / three[i]) % 3; // digit at position i
if (d > 0)
dp[j - d * three[i]] += dp[j];
}
}
// Process each query: check whether the lower m digits of mask (precomputed in low[])
// are compatible with the current prefix (via the lookup table "valid"). If so,
// add dp[high part] to the answer.
for (int j = 0; j < q; j++){
if (!valid[pref][low[j]])
continue;
ans[j] += dp[high[j]];
}
}
for (int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
