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

You are given a binary string <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b867005672a53a90079685a121443181793694d7.png" style="max-width: 100.0%;max-height: 100.0%;"/> and an integer <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/be942ae2800fe456a9cd1c9c63aa053db9c70c46.png" style="max-width: 100.0%;max-height: 100.0%;"/>. Find the number of integers *k*, 0 ≤ *k* &lt; *N*, such that for all *i* = 0, 1, ..., *m* - 1
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·10<sup class="upper-index">5</sup>).

Each of the next *n* lines contains two space-separated integers *p*<sub class="lower-index">*i*</sub>, α<sub class="lower-index">*i*</sub> (1 ≤ *p*<sub class="lower-index">*i*</sub>, α<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>, *p*<sub class="lower-index">*i*</sub> is prime). All *p*<sub class="lower-index">*i*</sub> are distinct.
none
MOD = 10**9 + 7

# Function to calculate modular inverse using Extended Euclidean Algorithm
def mod_inv(a, m):
    m0 = m
    y, x = 0, 1

    if m == 1:
        return 0

    while a > 1:
        q = a // m
        m, a = a % m, m
        x, y = y - q * x, x

    if y < 0:
        y += m0

    return y

# Function to find the number of integers k modulo pi that satisfy the condition
def find_k_mod_pi(s, pi):
    k_mod_pi = 0
    n = len(s)

    # Calculate the value of s in base-pi
    for i in range(n):
        k_mod_pi = (k_mod_pi * pi + int(s[i])) % pi

    # Calculate m (m = pi^len(s))
    m = pow(pi, n, MOD)

    # Calculate the modular inverse of m modulo pi
    m_inv = mod_inv(m, pi)

    # Calculate the number of integers k modulo pi that satisfy the condition
    num_integers_k = (pi - k_mod_pi) * m_inv % pi

    return num_integers_k

# Read input
s = input()
n = int(input())

ans = 1

# Process each prime and update the final answer using CRT
for _ in range(n):
    pi, alpha_i = map(int, input().split())
    num_integers_k = find_k_mod_pi(s, pi)
    ans = (ans * pow(pi, alpha_i - num_integers_k, MOD)) % MOD

print(ans)
