该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小$A$出了一道题目：给定一个长度为$N$的正整数序列，$a_1,a_2....a_n$和一个正整数$K$。想要让东东爸 生成一个长度为$N$的正整数序列$b_1,b_2....b_n$(其中$1\le b_i\le a_i$),使得$LCM(b_1,b_2....b_n,K)$等于 $K$,问能构造出多少个这样的$b$序列？

输入描述

第一行两个整数 $N$, $M$。$M$表示询问个数。

接下来一行$N$个正整数，表示$a_1,a_2....a_n$。

接下来$M$行，每行对应一个正整数$K$。

输出描述

对于每个给定的$K$，输出一行。

当然$ans$可能很大，需要模$10^9+7$输出。

Samples

3 2
1 2 3
3
4

2
4

200 50
31 169 85 179 66 187 128 77 132 91 119 81 125 98 97 12 195 34 52 160 179 162 176 139 174 26 50 145 36 7 152 115 89 163 17 181 171 108 24 57 95 10 37 101 87 173 162 38 45 125 22 74 20 24 51 182 52 113 56 108 58 165 104 107 57 118 118 93 35 92 37 9 46 143 33 69 135 189 5 66 72 164 52 189 130 144 103 18 9 170 2 127 11 157 109 1 46 100 107 65 108 194 53 174 88 81 133 144 102 90 34 184 125 103 47 65 76 123 106 181 174 20 78 104 78 141 152 62 105 33 130 43 198 103 25 182 38 154 63 78 148 116 49 161 140 54 167 183 107 24 197 41 187 169 29 17 51 22 185 88 57 51 137 43 64 35 42 147 159 128 73 127 15 162 82 131 147 144 20 14 126 16 169 181 151 22 110 17 11 167 24 41 94 140 129 129 74 150 102 196 
180 163 113 92 2 53 53 160 21 92 149 178 118 171 92 113 42 46 83 176 62 25 69 16 9 44 59 177 133 39 118 89 100 165 88 171 194 124 170 103 87 23 196 119 98 40 47 117 85 79 

668369112
179869065
986564553
69708354
249722536
747597154
747597154
670147871
369141859
69708354
743685088
824631148
676764619
904520404
69708354
986564553
222082415
71224046
867021468
828029407
21795249
620851615
953271634
936202834
352410776
63873420
896465609
344943500
681975381
441746881
676764619
804188847
666976566
267782704
846285121
904520404
235938774
227027076
794652477
747046415
99857430
581415240
235145802
369256605
81951325
524407517
769740174
106123593
942319727
936171702

数据范围

对于 $10\%$ 的数据，$1≤K、N≤5，1≤a_i≤5,M≤5$。

对于 $20\%$ 的数据，$1≤K、N≤100，1≤a_i≤100,M≤20$。

对于 $30\%$ 的数据，$1≤K、N≤200，1≤a_i≤200,M≤50$。

对于 $40\%$ 的数据，$1≤K、N≤500，1≤a_i≤500,M≤100$。

对于 $50\%$ 的数据，$1≤K、N≤1000，1≤a_i≤1000,M≤100$。

对于 $60\%$ 的数据，$1≤K、N≤2000，1≤a_i≤2000,M≤100$。

对于 $100\%$ 的数据，$1≤K、N≤10^5，1≤a_i≤10^5 ， M≤100$。

数据有一定梯度。