time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Ayrat has number n, represented as it’s prime factorization pi of size m, i.e. n = p1·p2·…·pm. Ayrat got secret information that that the product of all divisors of n taken modulo 109 + 7 is the password to the secret data base. Now he wants to calculate this value.
Input
The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) — the number of primes in factorization of n.
The second line contains m primes numbers pi (2 ≤ pi ≤ 200 000).
Output
Print one integer — the product of all divisors of n modulo 109 + 7.
Examples
input
2
2 3
output
36
input
3
2 3 2
output
1728
Note
In the first sample n = 2·3 = 6. The divisors of 6 are 1, 2, 3 and 6, their product is equal to 1·2·3·6 = 36.
In the second sample 2·3·2 = 12. The divisors of 12 are 1, 2, 3, 4, 6 and 12. 1·2·3·4·6·12 = 1728.
【题解】
数论问题;先搞出质数的总数a[0];存在a[1..a[0]]中;
用cnt[x]表示x这个数字的数目;
用l[n]表示∏(cnt[a[i]]+1);i=1..n
用r[n]表示∏(cnt[a[i]]+1);i=n..a[0];
则枚举每个数字a[i];
对于1..i-1和i+1..a[0]这些数字;
它们的组合有l[i-1]*r[i+1]个;
a[i]要参与到这些组合中;
那么最后会乘进去多少个a[i]呢;
显然a[i]^x就会乘进去x个a[i];
即
(a[i]^1)^(l[i-1]*1*r[i+1])
(a[i]^2)^(l[i-1]*2*r[i+1])
(a[i]^3)^(l[i-1]*3*r[i+1])
…
(a[i]^cnt[a[i]])^(l[i-1]*cnt[a[i]]*r[i+1])
最后会全部乘起来;
即a[i]^(l[i-1]r[i+1](1+2+3..+cnt[a[i]]))
即a[i]^(l[i-1]r[i+1]*cnt[a[i]](cnt[a[i]]+1)/2);
这个数字的指数是很恐怖的;
a[i]^(l[i-1]r[i+1]*cnt[a[i]](cnt[a[i]]+1)/2)
需要用费马小定理搞一搞；
下面是证明;
最上面那行是费马小定理;
这个费马小定理要求p和a是互质的;
而P是1e9+7是质数
a[i]最大20W小于P显然a[i]和p互质;则
a[i]^(l[i-1]r[i+1]*cnt[a[i]](cnt[a[i]]+1)/2) % p==a[i]^(l[i-1]r[i+1]*cnt[a[i]](cnt[a[i]]+1)/2%(p-1)) % p;
然后快速幂搞下就好;
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define lson L,m,rt<<1
#define rson m+1,R,rt<<1|1
#define LL long long
using namespace std;
const int MAXN = 2e5;
const int MOD = 1e9+7;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);
LL ans = 1,l[MAXN+100],r[MAXN+100],cnt[MAXN+100];
int m;
LL a[MAXN+100] = {0};
vector <LL> pre[MAXN];
void input_LL(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void input_int(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
LL ksm(LL a,LL x)
{
if (x==0)
return 1;
LL temp = ksm(a,x>>1);
temp = (temp*temp)%MOD;
if (x&1)
temp = (temp*a)%MOD;
return temp;
}
int main()
{
input_int(m);
for (int i = 1;i <= m;i++)
{
int x;
input_int(x);
cnt[x]++;
}
for (int i = 2;i <= MAXN;i++)
if (cnt[i])
a[++a[0]] = i;
l[0] = 1;r[a[0]+1] = 1;
for (int i = 1;i<=a[0];i++)
l[i] = (l[i-1]*(cnt[a[i]]+1))%(MOD-1);
for (int i = a[0];i>=1;i--)
r[i] = (r[i+1]*(cnt[a[i]]+1))%(MOD-1);
for (int i = 1;i <= a[0];i++)
{
LL temp1 = ((cnt[a[i]]*(cnt[a[i]]+1))/2)%(MOD-1);
LL temp2 = (l[i-1]*r[i+1])%(MOD-1);
LL temp = ksm(a[i],(temp1*temp2)%(MOD-1));
ans = (ans * temp)%MOD;
}
printf("%I64d
",ans);
return 0;
}