#P3462. DZY Loves Math II

    ID: 2662 传统题 1000ms 512MiB 尝试: 347 已通过: 143 难度: 8 上传者: 标签>CF2500省选/NOI-试除法分解质因数普通生成函数生成函数求系数多重背包差分转化滚动数组插板法组合数乘法递推模逆元

DZY Loves Math II

题目描述

给定一个正整数 SS。对每个询问的正整数 nn,求有多少个非空的质数序列 p1≤p2≤⋯≤pkp_1\le p_2\le\cdots\le p_k 满足

$$\sum_{i=1}^k p_i=n,\qquad \operatorname{lcm}(p_1,\ldots,p_k)=S.$$

同一个质数可以出现多次。答案对 109+710^9+7 取模。

输入格式

第一行两个正整数 S,qS,q,其中 qq 是询问数量。接下来 qq 行,每行一个正整数 nn。

输出格式

输出 qq 行,每行一个整数,表示对应询问的答案对 109+710^9+7 取模的结果。

样例

30 3
9
29
1000000000000000000
0
9
450000036

数据范围

对于所有数据,2≤S≤2×1062\le S\le 2\times10^6,1≤n≤10181\le n\le10^{18},1≤q≤1051\le q\le10^5。

原题定义图