Codeforces Round #232 (Div. 2) C

1
15

1

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<map>
 5 typedef long long LL;
 6 using namespace std;
 7 const int MAX =600;
 8 const int F = 1e6+10;
 9 const int MOD = 1e9+7;
10 map<int , int > m;
11 int a[MAX];
12 LL c[30000][MAX];
13 void getp(int n)
14 {
15     long long i;
16     for(i=2;(long long)i*i<=n;i++)
17     {
18         while(n%i==0)
19         {
20             m[i]++;
21             n/=i;
22         }
23     }
24     if( n != 1 ) m[n]++;
25 }
26 void init()
27 {
28     c[0][0]=1;
29     for(int i=0;i<20020;i++)
30     {
31         c[i][i]=c[i][0]=1;
32         for(int j=1;j<=min(i,MAX);j++)
33         {
34             c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
35         }
36     }
37 }
38 int main()
39 {
40     int n;
41     LL ans;
42     while(scanf("%d",&n)==1)
43     {
44         m.clear(); ans=1;
45         for(int i=0;i<n;i++)
46         {
47             scanf("%d",&a[i]);
48             getp(a[i]);
49         }
50         init();
51         //printf("s");
52         for(map<int,int> ::iterator it=m.begin();it!=m.end();it++)
53         {
54             int k=it->second;
55             ans=ans*c[k-1+n][n-1]%MOD;
56         }
57         printf("%I64d\n",ans);
58     }
59     return 0;