Problem: If you have gone that far, you'll probably skip unnecessary legends anyway...

You are given a binary string <image> and an integer <image>. Find the number of integers k, 0 ≤ k < N, such that for all i = 0, 1, ..., m - 1

<image> Print the answer modulo 109 + 7.

Input

In the first line of input there is a string s consisting of 0's and 1's (1 ≤ |s| ≤ 40).

In the next line of input there is an integer n (1 ≤ n ≤ 5·105).

Each of the next n lines contains two space-separated integers pi, αi (1 ≤ pi, αi ≤ 109, pi is prime). All pi are distinct.

Output

A single integer — the answer to the problem.

Examples

Input

1
2
2 1
3 1


Output

2


Input

01
2
3 2
5 1


Output

15


Input

1011
1
3 1000000000


Output

411979884

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct node {
  long long val;
  int num;
};
node p[500002], a[5000002], b[5000002];
char s[42];
int n, side, f[42], mul, ans, len, cnt, zero;
long long ss;
const int P = 1e9 + 7;
bool cmp(node x, node y) { return x.val < y.val; };
int quick(int x, int y) {
  int res = 1, base = x;
  for (; y; y >>= 1) {
    if (y & 1) res = 1LL * res * base % P;
    base = 1LL * base * base % P;
  }
  return res;
}
void init() {
  scanf("%s", s + 1);
  len = strlen(s + 1);
  zero = 0;
  ss = 0;
  for (int i = 1; i <= len; ++i)
    if (s[i] == '0')
      ss <<= 1, zero++;
    else
      ss = (ss << 1) | 1;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i].val, &p[i].num);
  sort(p + 1, p + n + 1, cmp);
  for (side = 1; p[side].val <= len && side <= n; ++side)
    ;
}
void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
void DO_IT() {
  int last;
  cnt = 1;
  a[1].val = (1LL << len) - 1;
  a[1].num = 1;
  for (int i = 1; i < side; ++i) {
    last = cnt;
    cnt = 0;
    for (int j = 0; j < p[i].val; ++j) {
      long long S = 0;
      for (int k = j; k < j + len; ++k)
        if (!(k % p[i].val))
          S <<= 1;
        else
          S = (S << 1) | 1;
      if (S & ss != ss) break;
      for (int k = 1; k <= last; ++k)
        if (((a[k].val & S) & ss) == ss)
          b[++cnt].val = a[k].val & S, b[cnt].num = a[k].num;
    }
    sort(b + 1, b + cnt + 1, cmp);
    last = cnt;
    cnt = 0;
    for (int j = 1; j <= last; ++j)
      if (j == 1 || b[j].val != b[j - 1].val)
        a[++cnt] = b[j];
      else
        inc(a[cnt].num, b[j].num);
  }
  for (int i = 1; i <= cnt; ++i) {
    int t = 0;
    long long V = a[i].val;
    for (int j = len; j; --j, V >>= 1)
      if (!(V & 1)) ++t;
    inc(f[t], a[i].num);
  }
  for (int i = side; i <= n; ++i) {
    for (int j = zero; j; --j)
      f[j] = (1LL * (p[i].val - len + j) * f[j] % P +
              1LL * f[j - 1] * (zero - j + 1) % P) %
             P;
    f[0] = 1LL * f[0] * (p[i].val - len) % P;
  }
  mul = 1;
  for (int i = 1; i <= n; ++i)
    mul = 1LL * mul * quick(p[i].val, p[i].num - 1) % P;
  ans = 1LL * f[zero] * mul % P;
}
int main() {
  init();
  DO_IT();
  cout << ans;
  return 0;
}