← 返回题目列表

Codeforces · 765/G

G. 数学,数学无处不在

中文机器翻译题面 查看原题

如果你已经走了那么远,你可能会跳过不必要的图例......

给定一个二进制字符串 $$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