A10840 | Math, math everywhere

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

You are given a binary string  and an integer . Find the number of integers $k$ , $0<=k<N$ , such that for all $i=0$ , $1$ , ..., $m-1$

 Print the answer modulo $10^{9}+7$ .

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^{5}$ ).

Each of the next $n$ lines contains two space-separated integers $p_{i}$ , $α_{i}$ ( $1<=p_{i},α_{i}<=10^{9}$ , $p_{i}$ is prime). All $p_{i}$ are distinct.

A single integer — the answer to the problem.