Cerința

După ce au trecut sărbătorile, ca în fiecare an, Moș Crăciun a început să facă inventarul cadourilor rămase pentru anul următor. El are N cadouri și pe fiecare cadou este scris un număr natural. În fiecare an Moș Crăciun trebuie să noteze într-un carnețel cantitatea de fericire pe care o aduc aceste cadouri copiilor.

Pentru a calcula această valoare, prima dată el trebuie să înmulțească toate numerele înscrise pe cele N cadouri. Astfel el obține un număr foarte mare. Apoi el știe că numărul de divizori al acestui număr este cantitatea de fericire pe care el trebuie să o scrie în carnețel. Ajutați-l pe Moș Crăciun să afle cantitatea de fericire a celor N cadouri. Deoarece acest număr este foarte mare voi trebuie sa aflați doar restul împărțirii la 1.000.000.007.

Date de intrare

Pe prima linie a fișierului de intrare ​cadouri2.in​ se află numărul natural N. Pe următoarea linie se află N numere naturale reprezentând numerele care sunt scrise pe cele N cadouri.

Date de ieșire

In fișierul de ieșire ​cadouri2.out ​trebuie să se afle un singur număr care reprezintă cantitatea de fericire a celor N cadouri modulo 1.000.000.007

Restricții și precizări

• 1 ≤ N ≤ 1000
• Numerele înscrise pe cadouri sunt numere naturale cuprinse între 1 și 10​6
• Pentru teste în valoare de ​40 de puncte​, produsul celor N numere este ≤ 10​​9
• Pentru alte ​10 puncte​, produsul celor N numere este ≤ 10​​12
• Pentru alte ​20 de puncte, ​numerele înscrise pe cadouri sunt cuprinse între 1 și 1000

Exemplu 1:

cadouri2.in

3 
2 3 4

cadouri2.out

8

Explicație

Produsul celor trei numere este 24. Divizorii acestui număr sunt: 1, 2, 3, 4, 6, 8, 12, 24. În total 8 divizori.

Exemplu 2:

cadouri2.in

5 
12 24 3 7 15

cadouri2.out

120

Explicație

Produsul celor 5 numere este 90720. Acest număr are 120 de divizori.