所以gcd好求，把lcm转化为gcd的性质：

本质是min-max容斥，质因数分解对应指数取min、max的容斥

后面就不是按照题解来的了

枚举gcd=d，可以预处理出，ai有多少子集gcd为d，开个桶容斥一下即可

有指数的-1或者1的要求，和T的奇偶性有关，就记录一下0/1表奇偶性即可

注意gcd的范围是1~1e6

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define int long longusing namespace std;typedef long long ll;template
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=50000+5;const int M=1000000+5;const int U=1000000;const int mod=1e9+7;int qm(int x,int y){    int ret=1;while(y){        if(y&1) ret=(ll)ret*x%mod;x=(ll)x*x%mod;y>>=1;    }    return ret;}ll iv2;int n;int pw[N];ll f[M];int g[M][2];int a[N],buc[M];int ad(int x,int y){    return (x+y)%mod;//>=mod?x+y-mod:x+y;}int main(){    rd(n);    pw[0]=1;    for(reg i=1;i<=n;++i) rd(a[i]),buc[a[i]]++,pw[i]=pw[i-1]*2%mod;    iv2=qm(2,mod-2);    for(reg i=1;i<=U;++i){        int cnt=0;        for(reg j=i;j<=U;j+=i){            cnt+=buc[j];        }        if(cnt) {            g[i][0]=ad((ll)pw[cnt-1],mod-1);            g[i][1]=(pw[cnt-1]);        }    }    for(reg i=U;i>=1;--i){        for(reg j=i+i;j<=U;j+=i){            g[i][0]=ad(g[i][0],mod-g[j][0]);            g[i][1]=ad(g[i][1],mod-g[j][1]);        }    }    f[0]=0;f[1]=1;    for(reg i=2;i<=U;++i){        f[i]=ad(f[i-1],f[i-2]);    }    ll up=1,dw=1;    for(reg i=1;i<=U;++i){        up=up*qm(f[i],g[i][1])%mod;        dw=dw*qm(f[i],g[i][0])%mod;    }//    cout<<(ll)f[39]*f[104]%mod*qm(f[13],mod-2)%mod<