Tres-Veltör y su Inversión


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Hace unos días el joven vikingo Tres-Veltör comenzó a trabajar en el Instituto de Programadores Vikingos Contra la Estafa (IPVCE por sus siglas). Su trabajo normalmente consiste en investigar las compañías en internet que podrían ser una estafa y por lo tanto, supondría un riesgo para la economía de sus amigos. Hoy Tres-Veltör esta algo confundido ya que descubrió una nueva compañía llamada Trust Investing así que llamó a su mejor amigo del IPVCE Freddy-Verum, un vikingo experto en criptomonedas.

Este le propone invertir un arreglo a de tamaño N y si gana algún dinero decidirán confiar en la compañía. Su inversión funciona de la siguiente manera: La compañía escoge un subconjunto no vacío al azar del arreglo de Tres-Veltör, si el resultado de multiplicar todos los números del subconjunto es un cuadrado perfecto Tres-Veltör gana el 200\% de su inversion inicial, en otro caso la compañía quiebra y se lleva los arreglos de los inversores para venderlos en una tienda de regalos.Tres-Veltör ya invirtió su parte y ahora esta preocupado por perderlo todo, así que él quiere saber en cuantos casos puede ganar y en cuantos perder.

Un subconjunto del conjunto original es un conjunto formado eliminando 0, 1, varios o todos los elementos del conjunto original. Por ejemplo si el conjunto es \{1,2,5,10,34\} entonces \{1,5\}, \{1,2,5,10,34\} son subconjuntos del conjunto original, sin embargo \{1,2,1\} y \{1,2,5,10,34,100\} no lo son.

Entrada

La primera linea contiene el entero N (1 \leq N \leq 5*10^4).

La siguiente linea contiene el arreglo a (1 \leq a_i \leq 10^5) de tamaño N.

Salida

Una unica linea con dos números, la cantidad de casos en los que Tres-Veltör gana y la cantidad de casos en que pierde. Como estos números pueden ser muy grandes, imprímalos módulo 10^9+7 .

Subtareas

  • Subtareas 1 (5 puntos): Todos los elementos de a son números primos.
  • Subtareas 2 (5 puntos): 1 \leq N \leq 20.
  • Subtareas 3 (10 puntos): 1 \leq N \leq 40.
  • Subtareas 4 (20 puntos): 1 \leq N \leq 100,\ 1 \leq a_i \leq 70.
  • Subtareas 5 (40 puntos): 1 \leq a_i \leq 70.
  • Subtareas 6 (20 puntos): Sin restricciones adicionales.

Ejemplo #1 de Entrada

7
1 1 1 1 1 1 1

Ejemplo #1 de Salida

127 0

Ejemplo #2 de Entrada

30 40 27 3 10

Ejemplo #2 de Salida

7 24

Comments

There are no comments at the moment.