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;
static constexpr long long MOD = 1000000007ll;
int T;
string s;
int N, K;
int p[500010], e[500010];
map<long long, int> mp[20];
long long power(long long x, long long n) {
  long long result = 1;
  while (n) {
    if (n & 1) result = result * x % MOD;
    x = x * x % MOD;
    n = n / 2;
  }
  return result;
}
void update_mp(void) {
  int i, j;
  mp[0][0]++;
  for (i = 0; i < K; ++i) {
    int pr = p[i];
    vector<long long> masks(pr);
    for (int j = 0; j < T; ++j) masks[j % pr] |= (1ll << j);
    for (const auto& e : mp[i]) {
      long long mask = e.first;
      int cnt = e.second;
      for (int j = 0; j < pr; ++j) {
        long long mask2 = (mask | masks[j]);
        mp[i + 1][mask2] = (mp[i + 1][mask2] + cnt) % MOD;
      }
    }
  }
}
long long dp[500010][50];
long long func(void) {
  int i, j;
  for (const auto& e : mp[K]) {
    long long mask = e.first;
    long long cnt = e.second;
    bool good = true;
    int covered = 0;
    for (int i = 0; i < T; ++i) {
      if (mask & (1ll << i)) {
        if (s[i] == '0') good = false;
        if (s[i] == '1') covered++;
      }
    }
    if (good) dp[K][covered] = (dp[K][covered] + cnt) % MOD;
  }
  int ones = 0;
  for (int i = 0; i < T; ++i)
    if (s[i] == '1') ones++;
  for (i = K; i < N; i++) {
    long long pr = p[i];
    for (int j = 0; j < ones + 1; ++j) {
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (pr - T)) % MOD;
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * j) % MOD;
      if (j < ones)
        dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (ones - j)) % MOD;
    }
  }
  return dp[N][ones];
}
int main(void) {
  int i;
  cin >> s >> N;
  for (int i = 0; i < N; ++i) cin >> p[i] >> e[i];
  T = s.length();
  for (int i = 0; i < T; ++i) s[i] = ((s[i] == '0') ? '1' : '0');
  long long prod = 1;
  for (int i = 0; i < N; ++i) prod = prod * power(p[i], e[i] - 1) % MOD;
  sort(p, p + N);
  K = 0;
  while (K < N && p[K] < 40) K++;
  update_mp();
  long long ans = func();
  ans = ans * prod % MOD;
  cout << ans << endl;
  return 0;
}