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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

import sys

raw_data = list()

for line in sys.stdin:
    raw_data.append(line)

string = raw_data[0].strip()
n = int(raw_data[1])
N = 1

for i in range(2, 2 + n):
    (a, b) = raw_data[i].split(' ')
    N *= pow(int(a), int(b))

cnt = 0

for i in range(0, N):
    idx = 0
    for j in string:
        g = gcd(N, i + idx)
        if j == '0':
            if g == 1:
                break
        else:
            if g != 1:
                break
        idx += 1
    if idx == len(string):
        cnt += 1

print(cnt % (pow(10, 9) + 7))
