#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = (1 << 20) + 10; ll l, q, dp1[MAXN], dp2[MAXN]; string s, t; void input() { cin >> l >> q >> s; } void calcDp() { for (int i = 0; i < (1 << l); i++) { dp1[i] = (s[i] - '0'); dp2[(1 << l) - 1 - i] = (s[i] - '0'); } for (int i = 0; i < l; i++) for (int j = 0; j < (1 << l); j++) { dp1[j] += (((j >> i) & 1)? dp1[j - (1 << i)]: 0); dp2[j] += (((j >> i) & 1)? dp2[j - (1 << i)]: 0); } } ll find1(int i, int cnt, int num) { if (i == l) return (cnt % 2 == 0? dp1[num]: -dp1[num]); if (t[i] == '?') return find1(i + 1, cnt, num * 2 + 1); if (t[i] == '0') return find1(i + 1, cnt, num * 2); return find1(i + 1, cnt + 1, num * 2) + find1(i + 1, cnt, num * 2 + 1); } ll find2(int i, int cnt, int num) { if (i == l) return (cnt % 2 == 0? dp2[num]: -dp2[num]); if (t[i] == '?') return find2(i + 1, cnt, num * 2 + 1); if (t[i] == '1') return find2(i + 1, cnt, num * 2); return find2(i + 1, cnt + 1, num * 2) + find2(i + 1, cnt, num * 2 + 1); } ll find3(int i, int num) { if (i == l) return (s[num] - '0'); if (t[i] == '0') return find3(i + 1, 2 * num); if (t[i] == '1') return find3(i + 1, 2 * num + 1); return find3(i + 1, 2 * num) + find3(i + 1, 2 * num + 1); } ll findAns() { int cnt1 = 0, cnt0 = 0; for (int i = 0; i < l; i++) { if (t[i] == '1') cnt1++; else if (t[i] == '0') cnt0++; } if (cnt1 <= cnt0 && cnt1 <= (l - cnt1 - cnt0)) return find1(0, 0, 0); if (cnt0 <= cnt1 && cnt0 <= (l - cnt1 - cnt0)) return find2(0, 0, 0); return find3(0, 0); } int main() { ios::sync_with_stdio(false); cin.tie(0); input(); calcDp(); for (int i = 0; i < q; i++) { cin >> t; cout << findAns() << '\n'; } return 0; }