Math, math everywhere

5000ms

524288K

Description:

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

You are given a binary string $\text{[math]}$ and an integer $\text{[math]}$ . Find the number of integers k, 0 ≤ k < N, such that for all i = 0, 1, ..., m - 1

$\text{[math]}$ Print the answer modulo 10⁹ + 7.

Input:

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⁵).

Each of the next n lines contains two space-separated integers p_i, α_i (1 ≤ p_i, α_i ≤ 10⁹, p_i is prime). All p_i are distinct.

Output:

A single integer — the answer to the problem.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

1011
1
3 1000000000

Sample Output:

411979884

Informação

Provedor Codeforces

Código CF765G