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;
const long long mod = 1000000007;
long long modpow(long long a, long long e) {
  if (e == 0) return 1;
  if (e == 1) return a;
  long long x = modpow(a * a % mod, e >> 1);
  if (e & 1) x = x * a % mod;
  return x;
}
long long bitrev(long long bits, int si) {
  long long ret = 0;
  for (int i = 0; i < (si); ++i)
    if (bits & (1LL << i)) {
      ret |= 1LL << (si - 1 - i);
    }
  return ret;
}
bool symmetric = false;
int slen;
long long forbidden, required;
int nforb;
vector<int> hips;
vector<int> dp[41];
long long sol(int missing, int atp = 0) {
  if (atp == (int)(hips).size()) return missing == 0;
  int& out = dp[missing][atp];
  if (out != -1) return out;
  int p = hips[atp];
  int allowed = p - nforb;
  assert(allowed >= missing);
  long long res = 0;
  if (missing) res += missing * sol(missing - 1, atp + 1);
  res += (allowed - missing) * sol(missing, atp + 1);
  res %= mod;
  out = (int)res;
  return res;
}
struct Hasher {
  size_t operator()(unsigned long long x) const { return x + (x >> 13); }
};
unordered_map<long long, int, Hasher> mem;
vector<int> ps;
long long rec(long long bits, int at) {
  if (bits & forbidden) return 0;
  if (at == (int)(ps).size()) {
    int missing = (int)__builtin_popcountll(required & ~bits);
    return sol(missing);
  }
  if (symmetric && at <= 3) {
    bits &= (1LL << slen) - 1;
    long long bits2 = bitrev(bits, slen);
    if (bits2 < bits) bits = bits2;
  }
  int p = ps[at];
  long long lubits = bits;
  if (p >= 23) {
    bits &= (1LL << slen) - 1;
    int diff = slen - p;
    long long midm = ((1LL << (slen - 2 * diff)) - 1) << diff;
    long long mid = (bits & midm) >> diff;
    size_t ones = __builtin_popcountll(mid);
    long long sorted = (1LL << ones) - 1;
    lubits = (bits & ~midm) | (sorted << diff);
  }
  lubits = lubits << 20 | at;
  int& out = mem[lubits];
  if (out) return out - 1;
  long long bits2 = 0;
  for (int j = 0; j < 40; j += p) bits2 |= 1LL << j;
  long long mask = (1LL << 40) - 1;
  long long res = 0;
  long long bits3 = bits | bits2;
  long long base = rec(bits3, at + 1);
  res += base;
  for (int i = 0; i < (p - 1); ++i) {
    bits2 <<= 1;
    bits2 &= mask;
    long long bits4 = bits | bits2;
    if (bits4 == bits3)
      res += base;
    else
      res += rec(bits4, at + 1);
  }
  res %= mod;
  out = (int)(res + 1);
  return res;
}
int main() {
  cin.sync_with_stdio(false);
  cin.exceptions(cin.failbit);
  string s;
  cin >> s;
  ::slen = (int)(s).size();
  required = forbidden = 0;
  nforb = 0;
  string rev;
  for (int i = 0; i < (slen); ++i) {
    if (s[i] == '0')
      required |= 1LL << i;
    else
      forbidden |= 1LL << i, nforb++;
    rev = s[i] + rev;
  }
  if (s == rev) symmetric = true;
  int N;
  cin >> N;
  set<int> pss;
  long long mult = 1;
  for (int i = 0; i < (N); ++i) {
    int p, a;
    cin >> p >> a;
    if (p < slen)
      pss.insert(p);
    else
      hips.push_back(p);
    mult = mult * modpow(p, a - 1) % mod;
  }
  ps.assign(pss.begin(), pss.end());
  for (int i = 0; i < (41); ++i) dp[i].assign((int)(hips).size() + 1, -1);
  mem.reserve(3 << 23);
  long long res = rec(0LL, 0);
  cout << res * mult % mod << endl;
  exit(0);
}