题目大意
给定n个数(a_1)~(a_n)，定义(f_i)为斐波那契数列，求出(lcm(f_{a_1},...,f_{a_n}))，(nleq5 imes 10^4)，(a_ileq10^6)。
根据斐波那契的性质，有(gcd(f_n,f_m)=f_{gcd(n,m)})。
又根据常识，(lcm(n,m)=frac{nm}{gcd(n,m)})，(lcm(a,b,c)=frac{abc imes gcd(a,b,c)}{gcd(a,b) imes gcd(b,c) imes gcd(a,c)})，所以答案就是：
[prod_k f_k^{sum_S(-1)^{|S|+1}[gcd(S)=k]}
]
只看指数部分，(sum_S(-1)^{|S|+1}[gcd(S)=k]=sum_S(-1)^{|S|+1}[gcd(frac{S}{k})=1])
[=sum_{S}(-1)^{|S|+1}sum_{d|gcd(frac{S}{k})}mu(d)
\=sum_{d}mu(d)sum_{kd|S}(-1)^{|S|+1}
]
就相当于只选(kd)的倍数贡献是((-1)^{选的个数+1})，写出来就是(sum_{i=1}^{m}{mchoose i}(-1)^{i+1})，从一开始是因为不能不选，(m)是一共有多少个(kd)的倍数。就等于(-sum_{i=0}^m{mchoose i}(-1)^i+1=1 imes [m eq 0])。所以对于一个(k)，他的贡献就是(sum_{d=1}^{max{a_i}/k}mu(d) imes [exists x,kd|x])。复杂度(nln n)。
il int fpow(int a,int b,int ans=1){
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
return ans;
}
il int calc(cint &k){
rg int ans=0;
fp(i,1,mx/k)if(vis[i*k])ans=(ans+mu[i])%(mod-1);
return ans;
}
int main(){
n=rd();
fp(i,1,n)a[i]=rd(),mx=max(mx,a[i]);
mu[1]=1;
fp(i,2,mx){
if(!isnp[i])pri[++cnt]=i,mu[i]=mod-2;
for(rg int j=1;j<=cnt&&pri[j]*i<=mx;++j){
isnp[i*pri[j]]=1;
if(i%pri[j]==0)break;
mu[i*pri[j]]=mod-1-mu[i];
}
}
fp(i,1,n)for(rg int j=1;j*j<=a[i];++j)if(a[i]%j==0)vis[j]=vis[a[i]/j]=1;
f[1]=1; fp(i,2,mx)f[i]=(f[i-1]+f[i-2])%mod;
fp(i,1,mx)ans=1ll*ans*fpow(f[i],calc(i))%mod;
printf("%d
",ans);
return 0;
}