没啥意思的板子题。
首先，众所周知，
\[\gcd\{f_a,f_b\}=f_{\gcd\{a,b\}} \]所以考虑将 \(\operatorname{lcm}\) 转化为 \(\gcd\)。
\(\min-\max\) 容斥指出，
\[\max_{a\in S}a=\sum_{T\subseteq S,T\neq\varnothing}(-1)^{|T|-1}\min_{a\in T}a \]于是有推论
\[\mathop{\operatorname{lcm}}\limits_{a\in S}a=\prod_{T\subseteq S,T\neq\varnothing}(\gcd_{a\in T}a)^{(-1)^{|T|-1}} \]（对每个质因子做一次 \(\min-\max\) 反演）
于是只用计算每个 \(v=\gcd\limits_{a\in T}a\)，其 \(v\) 的幂次的贡献。
考虑到这需要 \(\gcd\) 卷积。
不妨设有全集 \(U\)，满足其为所有（考虑范围内的）数的倍数。
这样，我们即可用 \(\gcd\) 卷积描述其为
\[z^U-\prod_{a\in S}^{\gcd\text{卷积}}(z^U-z^a) \]众所周知这个形式可以使用 CF449D 的技巧，用 Dirichlet 前缀和可以对其优化。
然后就做完了。
核心代码很短。
const ullt Mod=1e9+7;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
int Cnt[2000005];
bol Gone[2000005];
modint F[2000005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n;scanf("%u",&n);
for(uint i=0,v;i<n;i++)
scanf("%u",&v),Cnt[v]++;
for(uint i=2;i<=1000000;i++)if(!Gone[i]){
for(uint j=1000000/i*i;j;j-=i)
Cnt[j/i]+=Cnt[j],Gone[j]=1;
Gone[i]=0;
}
F[1]=1;
for(uint i=1;i<=1000000;i++)
Cnt[i]=(bol)Cnt[i],F[i+1]=F[i]+F[i-1];
for(uint i=2;i<=1000000;i++)if(!Gone[i])
for(uint j=i;j<=1000000;j+=i)
Cnt[j/i]-=Cnt[j];
modint ans(1);
for(uint i=1;i<=1000000;i++)
ans*=Cnt[i]>=0?F[i]^Cnt[i]:F[i]^(((Mod-2)*-Cnt[i])%(Mod-1));
ans.println();
return 0;
}