Un Multiconjunto es un conjunto matemático que permite repeticiones. A usted se le da un multiconjunto ~A~ de enteros positivos con ~N~ elementos: ~A={A_1,A_2,...,A_N}~.

Puedes repetir la siguiente operación cualquier número de veces (posiblemente cero). Elige un entero positivo ~x~ que aparezca al menos dos veces en ~A~. Elimina dos ocurrencias de ~x~ de ~A~, y añade una ocurrencia de ~x+1~ a ~A~.

Encuentra el número de multiconjuntos que ~A~ puede ser al final.

Entrada

Leer desde la entrada estándar los datos en el siguiente formato:

N 
A_1,A_2,…,A_N

Salida

Imprime el número, módulo ~998244353~, de multiconjuntos que ~A~ puede ser al final. .

Restricciones

• ~1 \leq N \leq 2*10^5~
• ~1 \leq A_i \leq 2*10^5~

Ejemplo #1 de Entrada

4 
1 1 2 4

Ejemplo #1 de Salida

3

Ejemplo #2 de Entrada

5
1 2 3 4 5

Ejemplo #2 de Salida

1