#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <utility>
using std::pair;

const int MAXN = (1 << 17) + 5;
const int P = 1000000007;
const int D = 100001;
const double PI = acos(-1.);

char buffer[MAXN];
pair<double, double> pa[2][MAXN * 2], res[MAXN * 2], tmp[MAXN * 2];
int org[MAXN * 2], ans[MAXN];
int len_a, n, cnt;

inline int Lowbit(int x) { return x & -x; }

void Fill(pair<double, double> to[], int m, int d) {
  if (m == n) {
    to[d] = {org[cnt++], 0.};
  } else {
    Fill(to, m << 1, d);
    Fill(to, m << 1, d + m);
  }
}

void Fill2(pair<double, double> to[], int m, int d) {
  if (m == n) {
    to[d] = tmp[cnt++];
  } else {
    Fill2(to, m << 1, d);
    Fill2(to, m << 1, d + m);
  }
}

void FFT(pair<double, double> p[], double op) {
  for (int d = 0; (1 << d) < n; ++d) {
    int m = 1 << d;
    double p0 = PI / m * op;
    double sinp0 = sin(p0);
    double cosp0 = cos(p0);
    for (int i = 0; i < n; i += m << 1) {
      double sinp = 0;
      double cosp = 1;
      for (int j = 0; j < m; ++j) {
        double ta = cosp * p[i + j + m].first - sinp * p[i + j + m].second;
        double tb = cosp * p[i + j + m].second + sinp * p[i + j + m].first;
        p[i + j + m] = {p[i + j].first - ta, p[i + j].second - tb};
        p[i + j].first += ta;
        p[i + j].second += tb;
        double tsinp = sinp;
        sinp = sinp * cosp0 + cosp * sinp0;
        cosp = cosp * cosp0 - tsinp * sinp0;
      }
    }
  }
}

void Transform(pair<double, double> to[]) {
  cnt = 0;
  Fill(to, 1, 0);
  FFT(to, 1.);
}

void Mul(int t) {
  Transform(res);
  for (int i = 0; i < n; ++i) {
    tmp[i].first = res[i].first * pa[t][i].first - res[i].second * pa[t][i].second;
    tmp[i].second = res[i].first * pa[t][i].second + res[i].second * pa[t][i].first;
  }
  cnt = 0;
  Fill2(res, 1, 0);
  FFT(res, -1.);
}

void Init() {
  assert(scanf("%s", buffer) == 1);
  len_a = strlen(buffer);
  // Find the smallest power of 2 that is greater than or equal to length of A.
  for (n = len_a; n != Lowbit(n); n += Lowbit(n));
  // Double the total length because B can be as long as A.
  n *= 2;
  for (int i = 0; i < len_a; ++i) org[i] = buffer[i] == '1';
  for (int i = len_a; i <= n; ++i) org[i] = 0;
  Transform(pa[0]);
  for (int i = 0; i < len_a; ++i)
    org[i] ^= 1;
  Transform(pa[1]);
}

void Work() {
  assert(scanf("%s", buffer) == 1);
  int len_b = strlen(buffer);
  for (int i = 0; i < len_b; ++i) org[i] = buffer[len_b - 1 - i] == '1';
  for (int i = len_b; i <= n; ++i) org[i] = 0;
  Mul(1);
  for (int i = 0; i <= len_a - len_b; ++i)
    ans[i] = int(res[i + len_b - 1].first / n + 0.5);
  for (int i = 0; i < len_b; ++i) org[i] ^= 1;
  Mul(0);
  int hash_value = 0;
  for (int i = 0; i <= len_a - len_b; ++i) {
    int t = ans[i] + int(res[i + len_b - 1].first / n + 0.5);
    hash_value = ((long long)hash_value * D + t) % P;
  }
  printf("%d\n", hash_value);
}

int main() {
  Init();
  int cases;
  assert(scanf("%d", &cases) == 1);
  while (cases--) Work();
  return 0;
}