Informática - Nível Avançado - Semana 10

Divisores

São dados n inteiros a_1, a_2, ..., a_n. Cada a_i têm entre 3 e 5 divisores. Considere o produtório de todos os inteiros a_i. Encontre o número de divisores desse produtório. Formalmente, diga a quantidade de divisores de  p = \prod_{i=1}^{n} a_i.

Entrada:

A primeira linha da entrada contém um inteiro n, a quantidade de números.

Cada uma das próximas n linhas contém um inteiro a_i. É garantido que o número de divisores de a_i está entre 3 e 5.

Saída:

Imprima apenas um inteiro d, a quantidade de divisores de  p = \prod_{i=1}^{n} a_i módulo 998244353.

Restrições:

  • 1 \leq n \leq 500
  • 1 \leq a_i \leq 2*10^{18}

Exemplos:

Entrada Saida
3
9
15
143
32
Entrada Saida
8 
4606061759128693
4606066102679989
4606069767552943
4606063116488033
4606063930903637
4606064745319241
4606063930904021
4606065559735517
1920
Entrada Saida
3
4
8
16
10

Nota:

No primeiro exemplo p = 19305. Seus divisores são:

1, 3, 5, 9, 11, 13, 15, 27, 33, 39, 45, 55, 65, 99, 117, 135, 143, 165, 195, 297, 351, 429, 495, 585, 715, 1287, 1485, 1755, 2145, 3861, 6435, 19305. Um total de 32.

Para submeter sua solução, use esse link