题目描述

给定一个长度为 $m$ 的 $01$ 字符串 $s = s_{0} + s_{1} + \dots + s_{m-1}$ 和一个正整数 $n$ ，定义一个数 $x$ 是合法的，当且仅当，对于任意 $\forall 0 \leq i < m$ ，满足 $[\gcd(x+i,n)=1] = s_i$ （即若 $s_i=1$ 则 $\gcd(x+i,n)=1$ ，否则 $\gcd(x+i,n)=0$ ）。计算 $[0,n-1]$ 中合法的数的数量，对 $10^{9}+7$ 取模。

输入格式

输入的第一行包含一个 $01$ 字符串，表示 $s$ ，其中 $m$ 为字符串 $s$ 的输入长度。

输入的第二行包含一个正整数 $n'$ ，表示 $n$ 的质因子数量。

接下来 $n'$ 行每行两个正整数 $p_i,q_i$ ，表示 $n$ 的质因子 $p_i$ 的幂次为 $q_i$ ，保证输入的 $p_i$ 互不相同，即 $n = \prod_{i=1}^{n'} p_i^{q_i}$ 。

输出格式

输出一行一个整数，表示合法的数的数量，对 $10^{9}+7$ 取模的结果。

数据范围

对于 $100\%$ 的数据，保证 $1 \leq n' \leq 2 \times 10^{6}$ ，$1 \leq m \leq 40$ ，$1 \leq p_i , q_i \leq 10^{9}$ ，保证 $p_i$ 为质数且互不相同。

特殊性质 A：保证 $1 \leq n \leq 2 \times 10^{6}$ 。

特殊性质 B：保证 $n'=1$ 。

特殊性质 C：保证 $1 \leq n' \leq 100$。

特殊性质 D：保证 $p_i$ 从 $[2,10^{9}]$ 内的质数随机均匀选择。

样例输入

010
2
2 1
3 2

样例输出

6