G. Math, math everywheretime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputIf 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 109 + 7.InputIn 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·105).Each of the next n lines contains two space-separated integers pi, αi (1 ≤ pi, αi ≤ 109, pi is prime). All pi are distinct.OutputA single integer — the answer to the problem.ExamplesInput122 13 1Output2Input0123 25 1Output15Input101113 1000000000Output411979884
Input122 13 1
Output2
['brute force', 'dp', 'math', 'meet-in-the-middle', 'number theory', '*3200']