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