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