CF765G.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 109 + 7.

如果你已经看到这里，那大概率会直接跳过不必要的说明……

给定一个二进制字符串 和一个整数 。求满足如下条件的整数 $k$ 的个数（其中 $0 \le k < N$）：对所有 $i = 0, 1, \dots, m-1$，均有

将答案对 $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·105).

Each of the next n lines contains two space-separated integers p__i, α_i_ (1 ≤ p__i, α_i_ ≤ 109, p__i is prime). All p__i are distinct.

输入的第一行是一个由 0 和 1 组成的字符串 $ s $（$ 1 \leq |s| \leq 40 $）。

输入的第二行是一个整数 $ n $（$ 1 \leq n \leq 5 \cdot 10^5 $）。

接下来的 $ n $ 行中，每行包含两个用空格分隔的整数 $ p_i $、$ \alpha_i $（$ 1 \leq p_i, \alpha_i \leq 10^9 $，且 $ p_i $ 为质数）。所有 $ p_i $ 互不相同。

A single integer — the answer to the problem.

一个整数——该问题的答案。