数学无处不在
数学无处不在
- 时间限制：5 秒
- 内存限制：512 MiB
题目描述
给定一个长度为 (m) 的二进制字符串 [ s=s_0s_1\ldots s_{m-1}, ] 以及一个正整数的质因数分解 [ N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}. ]
求满足 (0\le k<N)，并且对每个 (i=0,1,\ldots,m-1) 都有 [ \gcd(k+i,N)=1\quad\Longleftrightarrow\quad s_i=1 ] 的整数 (k) 的个数。
答案对 (10^9+7) 取模。
输入格式
第一行输入一个仅由字符 0 和 1 组成的字符串 (s)。
第二行输入一个整数 (n)。
接下来 (n) 行，每行输入两个整数 (p_i,\alpha_i)，表示 (N) 的一个质因子及其指数。
保证所有 (p_i) 均为质数且两两不同。
输出格式
输出一个整数，表示满足条件的 (k) 的数量对 (10^9+7) 取模后的结果。
样例输入 1
1
2
2 1
3 1
样例输出 1
2
样例输入 2
01
2
3 2
5 1
样例输出 2
15
样例输入 3
1011
1
3 1000000000
样例输出 3
411979884
数据范围
对于所有数据：
- (1\le m=|s|\le 40)；
- (1\le n\le 5\cdot 10^5)；
- (1\le p_i,\alpha_i\le 10^9)；
- (p_i) 是质数，且所有 (p_i) 两两不同。
| 子任务编号 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 20 | (m\le 12)，(n\le 8)，且 (N\le 200000) |
| 2 | (m\le 18)，且 (n\le 30) | |
| 3 | 对所有 (i) 都有 (p_i>m) | |
| 4 | 40 | 无特殊限制 |
本 Hydro 版本使用平台标准档位，将内存限制设为 512 MiB。