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.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("cadouri2.in");
ofstream cout("cadouri2.out");
int f1[500001] , f2[1000];
int main()
{
    int n , x;
    long long cnt = 1;
    int a = 0;
    cin >> x;
    for(int i = 1 ; i <= x ; ++i)
    {
        cin >> n;
        int d = 2;
        while(n > 1)
        {
            int p = 0;
            while(n % d == 0) n /= d , p++;
            if(d <= 500000) f1[d] += p;
            else
            {
                f2[a]+=p;
                a++;
            }
            d++;
            if(d * d > n) d = n;
        }
    }
    for(int i = 0 ; i <= 500000 ; ++i)
    {
        if(f1[i]!=0)
            cnt = (1LL * cnt * (f1[i]+1)) % 1000000007;
    }
    for(int i = 0 ; i < a ; ++i)
    {
        cnt = (1LL * cnt * (f2[i]+1)) % 1000000007;
    }
    cout << cnt;
    return 0;
}