题目原件：tmp.png

题目描述

对于正整数 $S,n$，称$(p_1,p_2,\ldots,p_k)$($k$ 为任意正整数) 是$n$的 $S-$质数拆分，当且仅当:

1. $p1+p2+…+p_{k-1}+p_k=n$;
2. $p_1,p_2,…,p_{k-1},p_k$ 均为质数;
3. $p_1\le p_2\le\ldots\le p_{k-1}\le p_k$;
4. $\text{lcm}(p_1,p_2,…,p_{k-1},p_k)=S$,其中 $\text{lcm}$ 表示最小公倍数.

现给定一个正整数 $S$，以及一些正整数 $n$。对于每一个 $n$，分别求出其有多少个不同的 $S-$质数拆分。答案对$10^9+7$取模。

输入格式

第一行，两个正整数 $S$ 和 $q$，$q$ 表示询问数量。

接下来 $q$ 行，每行一个正整数 $n$。

输出格式

输出共 $q$ 行，分别为每个询问的答案。

样例

30 3
9
29
1000000000000000000

0
9
450000036

数据范围与约定

对于$100$的数据，$2\le S\le 2\times 10^6,1\le n\le 10^{18},1\le q\le10^5$.

鸣谢

感谢$\text{the Loser}$协助更正数据