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(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

s = input()
n = int(input())
N = 1
for i in range(n):
    l = input().split(" ")
    N *= int(l[0])**int(l[1])

k = []
for char in range(len(s)):
    if s[char] == '1':
        k.append(char)
        
count = 0
for j in range(N):
    for i in range(len(k)):
        if gcd(k[i] + j, N) == 1:
            count += 1
print(count)
