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⁹ + 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^{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.

Output

A single integer — the answer to the problem.