Ingredientes Alergênicos

#29
Made by: Rafael Grandsire
1024MB
0.3s

Na Nlogonia, as comidas são identificadas por números. Os números primos identificam os ingredientes básicos, e o número que identifica cada comida é dado pelo produto dos números associados aos ingredientes que a compõem, respeitando multiplicidades. Por exemplo, uma comida de número 12 contém duas unidades do ingrediente 2, e uma unidade do ingrediente 3, já que 12 = 2 · 2 · 3.

Você mora na Nlogonia, e é dono de um restaurante self-service, isto é, em que as pessoas montam seus próprios pratos com as comidas disponı́veis no restaurante. Você está aguardando atender $Q$ pessoas em seu restaurante hoje.

Cada pessoa tem um conjunto de alergias, que são identificadas por um número inteiro da mesma maneira: cada número primo que divide o número da pessoa indica que ela é alérgica ao ingrediente associado a esse número primo.

Dados os números associados a cada comida presente no seu restaurante, calcule, para cada uma das $Q$ pessoas, quantos pratos diferentes ela pode montar de forma que não haja nenhum ingrediente no prato ao qual ela seja alérgica.

Input

A primeira linha da entrada contém um inteiro $N$ $(1 ≤ N ≤ 10^5 )$, o número de comidas no seu restaurante. A próxima linha contém os números associados a cada comida $V_i$ $(1 ≤ V_i ≤ 10^6 )$.

A próxima linha contém um inteiro $Q$ $(1 ≤ Q ≤ 10^5 )$, o número de pessoas que vai comer no seu restaurante.

Seguem $Q$ linhas; a i-ésima delas contém um número $X_i$ $(1 ≤ X_i ≤ 10^6 )$, o número que representa as alergias da pessoa $i$.

Output

Para cada uma das $Q$ pessoas, imprima um número: a quantidade de pratos que podem ser montados com os ingredientes do restaurante, de forma que não esteja presente nenhum ingrediente ao qual a pessoa é alérgica. Como a resposta pode ser muito grande, imprima o resto de sua divisão por $10^9 + 7$.

Input Example
Output Example 
6
1 2 3 4 5 6
4
1
2
4
6

64
8
8
4

Explanation 1:
A primeira pessoa n˜ao tem nenhuma alergia, ent˜ao todas as 64 possibilidades de pratos s˜ao válidas para ela. Por outro lado, a última pessoa é alérgica às comidas que contêm os ingredientes associados aos números primos 2 e 3. Dessa forma, apenas 4 pratos s˜ao possíveis para ela: o prato vazio (sem nenhuma comida), o prato apenas com a comida 1 (que n˜ao tem nenhum ingrediente), o prato com a comida 5, e o prato com as comidas 1 e 5.