Se le dan ~N~ enteros ~A_{1}, A_{2},\dots,A_{N}~. Cada ~A_{i}~ tiene entre ~3~ y ~5~ divisores. Considere ~P = \displaystyle \prod_{i=1}^N A_{i}~ - el producto de todos los números enteros de entrada. Encuentra el número de divisores de ~P~. Como este número puede ser muy grande, imprímalo módulo ~998244353~.

Entrada

La primera línea contiene un solo entero ~ N (1 \leq N \leq 500 )~ - el número de números.

Cada uno de los siguientes ~N~ líneas contiene un número entero ~A_{i} (1 \leq A_{i} \leq 2\cdot 10^{18})~. Se garantiza que el número de divisores de cada ~A_{i}~ está entre ~3~ y ~5~.

Salida

Imprima un solo entero ~D~ - el número de divisores del producto ~A_{1} \cdot A_{2}\cdot \dots \cdot A_{N}~ módulo ~998244353~.

Puntuación

• Subtarea 1 (30 ptos): ~1 \leq A_{i} \leq 10^6~ para todo ~i~ tal que ~1 \leq i \leq n~.
• Subtarea 2 (70 ptos): Sin restricciones adicionales.

Ejemplos

Ejemplo de entrada 1

3
9
15
143

Ejemplo de salida 1

32

Ejemplo de entrada 2

1
7400840699802997

Ejemplo de salida 2

4

Ejemplo de entrada 3

8
4606061759128693
4606066102679989
4606069767552943
4606063116488033
4606063930903637
4606064745319241
4606063930904021
4606065559735517

Ejemplo de salida 3

1920

Ejemplo de entrada 4

3
4
8
16

Ejemplo de salida 4

10

Nota

En el primer caso, ~P = 19305~. Sus divisores son ~1,3,5,9,11,13,15,27,33,39,45,55,65,99,117,135,143,165,195,297,351,429,45,585,715,1287,1485,1755,2145,3861,6435,19305~, un total de ~32~.

En el segundo caso, ~P~ tiene cuatro divisores: ~1, 86028121, 86028157~ y ~7400840699802997~.

En el tercer caso ~P = 202600445671925364698739061629083877981962069703140268516570564888699375209477214045102253766023072401557491054453690213483547~.

En el cuarto caso, ~P = 512 = 2^9~, entonces la respuesta es igual a ~10~.