#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3119"
#include<iostream>
#include<vector>
#include"Mylib/Convolution/fast_mobius_transform_superset.cpp"
#include"Mylib/Convolution/fast_zeta_transform_superset.cpp"
#include"Mylib/IO/input_vector.cpp"
#include"Mylib/Number/Mint/mint.cpp"namespacehl=haar_lib;usingmint=hl::modint<1000000007>;intmain(){intn;std::cin>>n;autoa=hl::input_vector<int>(n);std::vector<int>dp(1<<20);for(autox:a)dp[x]+=1;dp=hl::fast_zeta_transform_superset(dp);std::vector<mint>f(1<<20);for(inti=0;i<1<<20;++i)f[i]=mint::pow(2,dp[i])-1;autoans=hl::fast_mobius_transform_superset(f);std::cout<<ans[0]<<std::endl;return0;}
#line 1 "test/aoj/3119/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3119"
#include<iostream>
#include<vector>
#line 2 "Mylib/Convolution/fast_mobius_transform_superset.cpp"
#include<cassert>
#include<functional>
#line 5 "Mylib/Convolution/fast_mobius_transform_superset.cpp"
namespacehaar_lib{template<typenameT,typenameFunc=std::minus<T>>std::vector<T>fast_mobius_transform_superset(std::vector<T>f,constFunc&op=std::minus<T>()){constintN=f.size();assert((N&(N-1))==0&&"N must be a power of 2");for(inti=1;i<N;i<<=1){for(intj=0;j<N;++j){if(not(j&i))f[j]=op(f[j],f[j^i]);}}returnf;}}// namespace haar_lib#line 5 "Mylib/Convolution/fast_zeta_transform_superset.cpp"
namespacehaar_lib{template<typenameT,typenameFunc=std::plus<T>>std::vector<T>fast_zeta_transform_superset(std::vector<T>f,constFunc&op=std::plus<T>()){constintN=f.size();assert((N&(N-1))==0&&"N must be a power of 2");for(inti=1;i<N;i<<=1){for(intj=0;j<N;++j){if(not(j&i))f[j]=op(f[j],f[j^i]);}}returnf;}}// namespace haar_lib#line 4 "Mylib/IO/input_vector.cpp"
namespacehaar_lib{template<typenameT>std::vector<T>input_vector(intN){std::vector<T>ret(N);for(inti=0;i<N;++i)std::cin>>ret[i];returnret;}template<typenameT>std::vector<std::vector<T>>input_vector(intN,intM){std::vector<std::vector<T>>ret(N);for(inti=0;i<N;++i)ret[i]=input_vector<T>(M);returnret;}}// namespace haar_lib#line 3 "Mylib/Number/Mint/mint.cpp"
#include<utility>namespacehaar_lib{template<int32_tM>classmodint{uint32_tval_;public:constexprstaticautomod(){returnM;}constexprmodint():val_(0){}constexprmodint(int64_tn){if(n>=M)val_=n%M;elseif(n<0)val_=n%M+M;elseval_=n;}constexprauto&operator=(constmodint&a){val_=a.val_;return*this;}constexprauto&operator+=(constmodint&a){if(val_+a.val_>=M)val_=(uint64_t)val_+a.val_-M;elseval_+=a.val_;return*this;}constexprauto&operator-=(constmodint&a){if(val_<a.val_)val_+=M;val_-=a.val_;return*this;}constexprauto&operator*=(constmodint&a){val_=(uint64_t)val_*a.val_%M;return*this;}constexprauto&operator/=(constmodint&a){val_=(uint64_t)val_*a.inv().val_%M;return*this;}constexprautooperator+(constmodint&a)const{returnmodint(*this)+=a;}constexprautooperator-(constmodint&a)const{returnmodint(*this)-=a;}constexprautooperator*(constmodint&a)const{returnmodint(*this)*=a;}constexprautooperator/(constmodint&a)const{returnmodint(*this)/=a;}constexprbooloperator==(constmodint&a)const{returnval_==a.val_;}constexprbooloperator!=(constmodint&a)const{returnval_!=a.val_;}constexprauto&operator++(){*this+=1;return*this;}constexprauto&operator--(){*this-=1;return*this;}constexprautooperator++(int){autot=*this;*this+=1;returnt;}constexprautooperator--(int){autot=*this;*this-=1;returnt;}constexprstaticmodintpow(int64_tn,int64_tp){if(p<0)returnpow(n,-p).inv();int64_tret=1,e=n%M;for(;p;(e*=e)%=M,p>>=1)if(p&1)(ret*=e)%=M;returnret;}constexprstaticmodintinv(int64_ta){int64_tb=M,u=1,v=0;while(b){int64_tt=a/b;a-=t*b;std::swap(a,b);u-=t*v;std::swap(u,v);}u%=M;if(u<0)u+=M;returnu;}constexprstaticautofrac(int64_ta,int64_tb){returnmodint(a)/modint(b);}constexprautopow(int64_tp)const{returnpow(val_,p);}constexprautoinv()const{returninv(val_);}friendconstexprautooperator-(constmodint&a){returnmodint(M-a.val_);}friendconstexprautooperator+(int64_ta,constmodint&b){returnmodint(a)+b;}friendconstexprautooperator-(int64_ta,constmodint&b){returnmodint(a)-b;}friendconstexprautooperator*(int64_ta,constmodint&b){returnmodint(a)*b;}friendconstexprautooperator/(int64_ta,constmodint&b){returnmodint(a)/b;}friendstd::istream&operator>>(std::istream&s,modint&a){s>>a.val_;returns;}friendstd::ostream&operator<<(std::ostream&s,constmodint&a){s<<a.val_;returns;}template<intN>staticautodiv(){staticautovalue=inv(N);returnvalue;}explicitoperatorint32_t()constnoexcept{returnval_;}explicitoperatorint64_t()constnoexcept{returnval_;}};}// namespace haar_lib#line 9 "test/aoj/3119/main.test.cpp"
namespacehl=haar_lib;usingmint=hl::modint<1000000007>;intmain(){intn;std::cin>>n;autoa=hl::input_vector<int>(n);std::vector<int>dp(1<<20);for(autox:a)dp[x]+=1;dp=hl::fast_zeta_transform_superset(dp);std::vector<mint>f(1<<20);for(inti=0;i<1<<20;++i)f[i]=mint::pow(2,dp[i])-1;autoans=hl::fast_mobius_transform_superset(f);std::cout<<ans[0]<<std::endl;return0;}