如果你已经走了那么远,你可能会跳过不必要的图例......
给定一个二进制字符串 $$s = s_0 \ldots s_{m-1}$$ 和一个整数 $$N = p_{1}^{\alpha_{1}} \ldots p_{n}^{\alpha_{n}}$$。查找整数 k, 0 ≤ k < N 的数量,使得对于所有 i = 0, 1, ..., m - 1
$$\gcd(k+i,N)=1 \text{ 当且仅当 } s_i=1$$
输入
在输入的第一行中有一个由 0 和 1 组成的字符串 s (1 ≤ |s| ≤ 40)。
在输入的下一行中有一个整数n (1 ≤ n ≤ 5·105)。
接下来的 n 行每行包含两个空格分隔的整数 pi, αi (1 ≤ pi, αi ≤ 109,pi 是质数)。所有 pi 都是不同的。
输出
一个整数——问题的答案。
示例
输入 #1
1 2 2 1 3 1
输出 #1
2
输入 #2
01 2 3 2 5 1
输出 #2
15
输入 #3
1011 1 3 1000000000
输出 #3
411979884