无额外样例。

问题描述

给出一个正整数 $M$，然后给出 $T$ 个问题：

每个问题给出一个正整数 $N$, 要求将 $N$ 表示成若干个质数的和，并且这些质数的最小公倍数恰好等于 $M$。

问：对于每个问题给出的 $N$, 你能找到多少种表示方案？答案可能很大，你需要将答案 mod $(10^9+7)$ 后输出。

注：两种表示方案不同，当且仅当存在一个质数，在两种表示方案中出现的次数不同。

输入

第一行：包含两个正整数 M, T

接下来 T 行，每行包含一个正整数 N

输出

共 T 行，每个问题的答案占一行

样例1输入

6 3
6
10
16

样例1输出

0
1
2

样例1解释

第一个问题：N = 6

找不到合法的表示方案。

第二个问题：N = 10

有 1 种不同的表示方案：10 = 2 + 2 + 3 + 3

第二个问题：N = 16

有两种不同的表示方案：

（1） 16 = 2 + 2 + 2 + 2 + 2 + 3 + 3

（2） 16 = 2 + 2 + 3 + 3 + 3 + 3

样例2输入

12345 5
12345
1234567890
98765432123456789
222222222222222222
1000000000000000000

样例2输出

5758
747202282
410222078
781602996
247630623

数据范围

$2 ≤ M ≤ 2×10^6, 1 ≤ T ≤ 10^5, 1 ≤ N ≤ 10^{18}$