|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
E - Paquetes de dulces
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
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.
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