#P15586. [2025年山东第一轮集训] 一切

    ID: 14798 传统题 5000ms 1024MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>数论组合数学动态规划搜索记忆化搜索算法基础模拟CF2800

[2025年山东第一轮集训] 一切

题目描述

给定一个长度为 mm 的 0101 字符串 s=s0+s1+⋯+sm−1s = s_{0} + s_{1} + \dots + s_{m-1} 和一个正整数 nn ,定义一个数 xx 是合法的,当且仅当,对于任意 ∀0≤i<m\forall 0 \leq i < m ,满足 [gcd⁡(x+i,n)=1]=si[\gcd(x+i,n)=1] = s_i (即若 si=1s_i=1 则 gcd⁡(x+i,n)=1\gcd(x+i,n)=1 ,否则 gcd⁡(x+i,n)=0\gcd(x+i,n)=0 )。计算 [0,n−1][0,n-1] 中合法的数的数量,对 109+710^{9}+7 取模。

输入格式

输入的第一行包含一个 0101 字符串,表示 ss ,其中 mm 为字符串 ss 的输入长度。

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

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

输出格式

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

数据范围

对于 100%100\% 的数据,保证 1≤n′≤2×1061 \leq n' \leq 2 \times 10^{6} ,1≤m≤401 \leq m \leq 40 ,1≤pi,qi≤1091 \leq p_i , q_i \leq 10^{9} ,保证 pip_i 为质数且互不相同。

测试点编号 m≤m \leq 特殊性质
1∼21 \sim 2 4040 A
3∼43 \sim 4 B
5∼75 \sim 7 1717 C
8∼108 \sim 10 4040 D
11∼1211 \sim 12 2323 无
13∼1413 \sim 14 2929
15∼2015 \sim 20 4040

特殊性质 A:保证 1≤n≤2×1061 \leq n \leq 2 \times 10^{6} 。

特殊性质 B:保证 n′=1n'=1 。

特殊性质 C:保证 1≤n′≤1001 \leq n' \leq 100。

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

样例输入

010
2
2 1
3 2

样例输出

6