fork download
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. const long long mod=1e9+7;
  6. int m, maxn,p; long long fp,prdt=1,d=1;
  7. vector<long long> cnt(2e5+1); // prime factors less than 2*10^5
  8.  
  9. long long modpow(long long a, long long x){
  10. long long e=1;
  11. while(x){
  12. if(x&1) e=e*a%mod;
  13. a=a*a%mod; x>>=1;
  14. }
  15. return e;
  16. }
  17. int main(){
  18. cin>>m; for(int i=1; i<=m; ++i) cin>>p, ++cnt[p], maxn=max(maxn,p);
  19. // Calculate product of divisors of a number from a given list of its prime factors
  20. /* EXAMPLE:
  21. (a^x * b^y * c^z * d^t)^(x+1)(y+1)(z+1)(t+1)
  22. = a^(x(x+1)/2 * (y+1)(z+1)(t+1))
  23. * b^(y(y+1)/2 * (x+1)(z+1)(t+1))
  24. * c^(z(z+1)/2 * (x+1)(y+1)(t+1))
  25. * d^(t(t+1)/2 * (x+1)(y+1)(z+1))
  26. */
  27. for(int num=2; num<=maxn; ++num) if(cnt[num]){
  28.  
  29. // For a prime p raised to the pow a, f(p^a) = p^(a(a+1)/2)
  30. fp = modpow(num, cnt[num]*(cnt[num]+1)/2) % mod;
  31.  
  32. // f(a*b) = f(a^d(b)) * f(b^d(a))
  33. // where d(a), d(b) denotes the num of div in a & b
  34. prdt = modpow(prdt, cnt[num]+1) * modpow(fp,d) % mod;
  35.  
  36. // The num of div d updated using Fermat’s Little Theorem:
  37. // a^(m–1) = 1 (mod m), extended to a^x = a^(x % (m–1)) (mod m)
  38. d = d * (cnt[num]+1) % (mod-1);
  39. }
  40. return cout<<prdt, 0;
  41. }
Success #stdin #stdout 0.01s 5500KB
stdin
3
2 3 2
stdout
1728