E - Paquetes de dulces

Time limit: 2 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

El mes pasado abrieron una tienda de dulces en el barrio de Fito y ya se está haciendo famosa por la variedad y calidad de su oferta. Entre los productos más vendidos están los paquetes de dulces. La tienda ofrece $N$ tipos de paquetes, cada uno con una cantidad fija de dulces de un mismo tipo.

Fito quiere probar muchos de estos dulces por lo que decide comprar varios paquetes, pero cada uno de un tipo diferente.  Como es aficionado a las matemáticas y especialmente a la Teoría de Números, se interesa sobremanera por aquellos conjuntos de paquetes con una propiedad algo rara: el máximo común divisor de las respectivas cantidades de dulces es exactamente $1$.

La tarea consiste en ayudar a Fito, a determinar la cantidad de formas distintas en que puede comprar conjuntos de paquetes de dulces, que tengan esa característica.

Input

La primera línea de la entrada es un entero $N (1 \leq N \leq 50)$ que indica la cantidad de tipos de paquetes de dulces que venden en la tienda. La segunda línea contiene $N$ enteros separados por un espacio, representando la cantidad dulces en cada tipo de paquete. Todos los paquetes tienen entre $1$ y $10^5$ dulces.

Output

La salida es un entero con la cantidad de formas distintas en que puede comprar Fito los paquetes de dulces. Como este número puede ser muy grande se debe imprimir su resto al dividirlo por $10000003$.

Sample test(s)

Input
4 2 4 5 6
Output
7