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 \le k \lt N, such that for all i=0, 1, ..., m-1 Print the answer modulo 109+7.

Input In the first line of input there is a string s consisting of 0's and 1's (1 \le |s| \le 40).In the next line of input there is an integer n (1 \le n \le 5 \cdot 105).Each of the next n lines contains two space-separated integers pi, \alpha i (1 \le pi, \alpha i \le 109, pi is prime). All pi are distinct.

Output A single integer- the answer to the problem.