#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define forr(a,b,c) for(int a=b;a<c;a++)
#define forrev(a,b,c) for(int a=b;a>c;a--)
#define all(v) v.begin(),v.end()
#define revall(v) v.rbegin(),v.rend()
#define allk(v,k) v.begin()+k,v.end()
#define revallk(v,k) v.rbegin()+k,v.rend()
#define allkj(v,k,j) v.begin()+k,v.end()-j
#define revallkj(v,k,j) v.rbegin()+j,v.rend()-k
#define ff first
#define ss second
#define init inity
////////////////////////// non-modifiable /////////////////////////////////
#define mod 1000000007
#define eps 1e-9
#define inf INT_MAX
#define infl LONG_LONG_MAX
ll power(ll a,ll n)
{
if(a==0)return 0;
if(a==1 || n==0)return 1;
if(n==1)return a%mod;//can remove mod?
ll t=power(a,n/2);
t=t*t%mod;
if(n&1)return t*a%mod;
return t;
}
#define P (int)(2e2)+9
#define FACTORIZE 1
#define DETERMINE 2
int primes[P];
void sieve(int prime=2)//2->detects prime, 1->max prime in factorization
{
forr(i,2,P-3)
{
if(!primes[i])
for(int j=prime*i;j<P-3;j+=i)primes[j]=i;
}
//forr(i,1,21)cout<<primes[i]<<" ";cout<<endl;
if(prime==2)
{
forr(i,1,P-3)
{
primes[i] = ( primes[i] == 0 );
}
}
else
primes[1] = 1;
}
int popcount(ll a)
{
int c=0;
while(a)
{
c++;
a-=a&-a;
}
return c;
}
void factorize(int a)
{
}
void update(int tree[],int idx,int val,int maxval)
{
for(;idx<=maxval;idx+=idx&-idx)
{
tree[idx]+=val;
//tree[idx]%=mod;
}
}
int read(int tree[],int idx)
{
ll sum=0;
for(;idx>0;idx-=idx&-idx)
{
sum+=tree[idx];
//sum%=mod;
}
return sum;
}
////////////////////////// MODIFIABLE /////////////////////////////////////
struct node2
{
int id,val;
node2()
{
static int ctx=0;
id=ctx++;
};
node2(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
{
val=a;
}
};
struct comp2
{
bool operator()(int a,int b)
{
//return a<b;
return b<a; //min heap
}
};
bool cmp2(int a,int b)
{
//return a<b;
return b<a;
}
struct node
{
int id,val;
node()
{
static int ctx=0;
id=ctx++;
};
node(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
{
val=a;
}
};
struct comp
{
bool operator()(int a,int b)
{
//return a<b;
return b<a; //min heap
}
};
bool cmp(int a,int b)
{
//return a<b;
return b<a;
}
////////////////////////// custom-defined /////////////////////////////////
#define N 100009
#define L ( (1 << 21) + 9 )
ll n,m,a[109],b,c,d,edge,k,h,w,x,y,p,q,t,ans,res,ma,mi,T,act=0,pas=1,cur,flag,now;
ll dp[2][L], dp2, cnt, square[109], conv[109], f[N];
char s[1];
//vector<string> s;
double e,z;
vector<int> v, vec;
set<int> sett;
typedef map<int,int> Mapp;
Mapp mapp;
////////////////////////// variable declarations //////////////////////////
void print()//for detailed output of [a data structure]
{
}
void print2()//for detailed output of [a data structure]
{
}
void input()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n;
forr(i,0,n)
{
cin >> x;
a[x]++;
}
}
void init()
{
sieve();
forr(i,1,71)
if( primes[i] == 1 )
conv[i] = k++;
//forr(i,1,71) cout << conv[i] << " "; cout << endl;
memset(primes,0,sizeof(primes));
sieve(1);
//forr(i,1,71) cout << primes[i] << " "; cout << endl;
forr(i,1,10)
square[i*i] = true;
//forr(i,1,71) cout << square[i] << " "; cout << endl;
f[0] = 1;
forr(i,1,N-4)
f[i] = f[i-1] * 2ll % mod;
//forr(i,1,10) cout << f[i] << " "; cout << endl;
}
inline int chooseEven(int n)
{
if( n == 1 ) return 0;
return ( f[n-1] - 1 + mod ) % mod;
}
inline int chooseOdd(int n)
{
return f[n-1];
}
inline int getMask(int num)
{
int mask = 0;
p = num;
//cout << "num=" << num << endl;
while( p > 1 )
{
//cout << "primes=" << primes[p] << endl;
mask ^= ( 1 << conv[ primes[p] ] );
p /= primes[p];
}
return mask;
}
void solve()
{
init();
b = 12 * 7;
//cout << "mask=" << getMask(b) << endl;
int lim = 1 << 21;
// handle 1s separately
forr(num,1,71)
{
if( a[num] > 0 )
{
if( square[ num ] == true )
dp[act][0] = ( f[ a[num] ] - 1 + mod ) % mod;
else
{
dp[act][0] = chooseEven( a[num] );
int mask = getMask(num);
dp[act][mask] = chooseOdd( a[num] );
}
p = num;
break;
}
}
forr(num,p+1,71)
{
if( a[num] == 0 ) continue;
act = 1 - ( pas = act );
memset(dp[act],0,sizeof(dp[act]));
int maskPrime = getMask(num);
forr(mask,0,lim)
{
dp[act][mask] += dp[pas][maskPrime];
dp[act][mask] %= mod;
if( maskPrime == 0 )
{
dp[act][mask] += 1ll * dp[pas][mask] * ( f[ a[num] ] - 1 + mod ) % mod;
dp[act][mask] %= mod;
dp[act][mask] += ( f[ a[num] ] - 1 + mod ) % mod;
dp[act][mask] %= mod;
continue;
}
dp[act][mask ^ maskPrime] += 1ll * dp[pas][mask] * chooseOdd(a[num]) % mod;
dp[act][mask ^ maskPrime] %= mod;
dp[act][mask] += 1ll * dp[pas][mask] * ( 1 + chooseEven(a[num]) ) % mod;
dp[act][mask] %= mod;
dp[act][mask] += chooseEven(a[num]);
dp[act][mask] %= mod;
}
}
}
void output()
{
cout << dp[act][0];
}
///////////////////////////// my functions ////////////////////////////////
int main()
{
input();
solve();
output();
return 0;
}
//// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN ////
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcGIoYSkgcHVzaF9iYWNrKGEpCiNkZWZpbmUgbXAoYSxiKSBtYWtlX3BhaXIoYSxiKQojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHBpaSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgcGxsIHBhaXI8bGwsbGw+CiNkZWZpbmUgZm9ycihhLGIsYykgZm9yKGludCBhPWI7YTxjO2ErKykKI2RlZmluZSBmb3JyZXYoYSxiLGMpIGZvcihpbnQgYT1iO2E+YzthLS0pCiNkZWZpbmUgYWxsKHYpIHYuYmVnaW4oKSx2LmVuZCgpCiNkZWZpbmUgcmV2YWxsKHYpIHYucmJlZ2luKCksdi5yZW5kKCkKI2RlZmluZSBhbGxrKHYsaykgdi5iZWdpbigpK2ssdi5lbmQoKQojZGVmaW5lIHJldmFsbGsodixrKSB2LnJiZWdpbigpK2ssdi5yZW5kKCkKI2RlZmluZSBhbGxraih2LGssaikgdi5iZWdpbigpK2ssdi5lbmQoKS1qCiNkZWZpbmUgcmV2YWxsa2oodixrLGopIHYucmJlZ2luKCkraix2LnJlbmQoKS1rCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBpbml0IGluaXR5Ci8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vIG5vbi1tb2RpZmlhYmxlIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwoKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIGVwcyAxZS05CiNkZWZpbmUgaW5mIElOVF9NQVgKI2RlZmluZSBpbmZsIExPTkdfTE9OR19NQVgKbGwgcG93ZXIobGwgYSxsbCBuKQp7CglpZihhPT0wKXJldHVybiAwOwoJaWYoYT09MSB8fCBuPT0wKXJldHVybiAxOwoJaWYobj09MSlyZXR1cm4gYSVtb2Q7Ly9jYW4gcmVtb3ZlIG1vZD8KCWxsIHQ9cG93ZXIoYSxuLzIpOwoJdD10KnQlbW9kOwoJaWYobiYxKXJldHVybiB0KmElbW9kOwoJcmV0dXJuIHQ7Cn0KI2RlZmluZSBQIChpbnQpKDJlMikrOQojZGVmaW5lIEZBQ1RPUklaRSAxCiNkZWZpbmUgREVURVJNSU5FIDIKaW50IHByaW1lc1tQXTsKdm9pZCBzaWV2ZShpbnQgcHJpbWU9MikvLzItPmRldGVjdHMgcHJpbWUsIDEtPm1heCBwcmltZSBpbiBmYWN0b3JpemF0aW9uCnsKCWZvcnIoaSwyLFAtMykKCXsKCQlpZighcHJpbWVzW2ldKQoJCWZvcihpbnQgaj1wcmltZSppO2o8UC0zO2orPWkpcHJpbWVzW2pdPWk7Cgl9CgkvL2ZvcnIoaSwxLDIxKWNvdXQ8PHByaW1lc1tpXTw8IiAiO2NvdXQ8PGVuZGw7CglpZihwcmltZT09MikKCXsKCQlmb3JyKGksMSxQLTMpCgkJewoJCQlwcmltZXNbaV0gPSAoIHByaW1lc1tpXSA9PSAwICk7CgkJfQoJfQoJZWxzZQoJCXByaW1lc1sxXSA9IDE7Cn0KaW50IHBvcGNvdW50KGxsIGEpCnsKCWludCBjPTA7Cgl3aGlsZShhKQoJewoJCWMrKzsKCQlhLT1hJi1hOwoJfQoJcmV0dXJuIGM7Cn0Kdm9pZCBmYWN0b3JpemUoaW50IGEpCnsKCQp9CnZvaWQgdXBkYXRlKGludCB0cmVlW10saW50IGlkeCxpbnQgdmFsLGludCBtYXh2YWwpCnsKCWZvcig7aWR4PD1tYXh2YWw7aWR4Kz1pZHgmLWlkeCkKCXsKCQl0cmVlW2lkeF0rPXZhbDsKCQkvL3RyZWVbaWR4XSU9bW9kOwoJfQp9CmludCByZWFkKGludCB0cmVlW10saW50IGlkeCkKewoJbGwgc3VtPTA7Cglmb3IoO2lkeD4wO2lkeC09aWR4Ji1pZHgpCgl7CgkJc3VtKz10cmVlW2lkeF07CgkJLy9zdW0lPW1vZDsKCX0KCXJldHVybiBzdW07Cn0KLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8gTU9ESUZJQUJMRSAvLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCgpzdHJ1Y3Qgbm9kZTIKewoJaW50IGlkLHZhbDsKCW5vZGUyKCkKCXsKCQlzdGF0aWMgaW50IGN0eD0wOwoJCWlkPWN0eCsrOwoJfTsKCW5vZGUyKGludCBhLGludCBiPTAsaW50IGM9MCxpbnQgZD0wLGludCBlPTAsaW50IGY9MCkKCXsKCQl2YWw9YTsKCX0KfTsKc3RydWN0IGNvbXAyCnsKCWJvb2wgb3BlcmF0b3IoKShpbnQgYSxpbnQgYikKCXsKCQkvL3JldHVybiBhPGI7CgkJcmV0dXJuIGI8YTsJLy9taW4gaGVhcAkKCX0KfTsKYm9vbCBjbXAyKGludCBhLGludCBiKQp7CgkvL3JldHVybiBhPGI7CglyZXR1cm4gYjxhOwp9CgpzdHJ1Y3Qgbm9kZQp7CglpbnQgaWQsdmFsOwoJbm9kZSgpCgl7CgkJc3RhdGljIGludCBjdHg9MDsKCQlpZD1jdHgrKzsKCX07Cglub2RlKGludCBhLGludCBiPTAsaW50IGM9MCxpbnQgZD0wLGludCBlPTAsaW50IGY9MCkKCXsKCQl2YWw9YTsKCX0KfTsKc3RydWN0IGNvbXAKewoJYm9vbCBvcGVyYXRvcigpKGludCBhLGludCBiKQoJewoJCS8vcmV0dXJuIGE8YjsKCQlyZXR1cm4gYjxhOwkvL21pbiBoZWFwCQoJfQp9Owpib29sIGNtcChpbnQgYSxpbnQgYikKewoJLy9yZXR1cm4gYTxiOwoJcmV0dXJuIGI8YTsKfQoKLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8gY3VzdG9tLWRlZmluZWQgLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCiNkZWZpbmUgTiAxMDAwMDkKI2RlZmluZSBMICggKDEgPDwgMjEpICsgOSApCmxsIG4sbSxhWzEwOV0sYixjLGQsZWRnZSxrLGgsdyx4LHkscCxxLHQsYW5zLHJlcyxtYSxtaSxULGFjdD0wLHBhcz0xLGN1cixmbGFnLG5vdzsKbGwgZHBbMl1bTF0sIGRwMiwgY250LCBzcXVhcmVbMTA5XSwgY29udlsxMDldLCBmW05dOwpjaGFyIHNbMV07Ci8vdmVjdG9yPHN0cmluZz4gczsKZG91YmxlIGUsejsKdmVjdG9yPGludD4gdiwgdmVjOwpzZXQ8aW50PiBzZXR0Owp0eXBlZGVmIG1hcDxpbnQsaW50PiBNYXBwOwpNYXBwIG1hcHA7Ci8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vIHZhcmlhYmxlIGRlY2xhcmF0aW9ucyAvLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwoKdm9pZCBwcmludCgpLy9mb3IgZGV0YWlsZWQgb3V0cHV0IG9mIFthIGRhdGEgc3RydWN0dXJlXQp7CgkKfQp2b2lkIHByaW50MigpLy9mb3IgZGV0YWlsZWQgb3V0cHV0IG9mIFthIGRhdGEgc3RydWN0dXJlXQp7CgkKfQp2b2lkIGlucHV0KCkKewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7Y2luLnRpZShOVUxMKTsKCWNpbiA+PiBuOwoKCWZvcnIoaSwwLG4pCgl7CgkJY2luID4+IHg7CgkJYVt4XSsrOwoJfQp9CnZvaWQgaW5pdCgpCnsKCXNpZXZlKCk7CgoJZm9ycihpLDEsNzEpCgkJaWYoIHByaW1lc1tpXSA9PSAxICkKCQkJY29udltpXSA9IGsrKzsKCgkvL2ZvcnIoaSwxLDcxKSBjb3V0IDw8IGNvbnZbaV0gPDwgIiAiOyBjb3V0IDw8IGVuZGw7CgoJbWVtc2V0KHByaW1lcywwLHNpemVvZihwcmltZXMpKTsKCXNpZXZlKDEpOwoKCS8vZm9ycihpLDEsNzEpIGNvdXQgPDwgcHJpbWVzW2ldIDw8ICIgIjsgY291dCA8PCBlbmRsOwoKCWZvcnIoaSwxLDEwKQoJCXNxdWFyZVtpKmldID0gdHJ1ZTsKCgkvL2ZvcnIoaSwxLDcxKSBjb3V0IDw8IHNxdWFyZVtpXSA8PCAiICI7IGNvdXQgPDwgZW5kbDsKCglmWzBdID0gMTsKCglmb3JyKGksMSxOLTQpCgkJZltpXSA9IGZbaS0xXSAqIDJsbCAlIG1vZDsKCgkvL2ZvcnIoaSwxLDEwKSBjb3V0IDw8IGZbaV0gPDwgIiAiOyBjb3V0IDw8IGVuZGw7Cn0KCmlubGluZSBpbnQgY2hvb3NlRXZlbihpbnQgbikKewoJaWYoIG4gPT0gMSApIHJldHVybiAwOwoJcmV0dXJuICggZltuLTFdIC0gMSArIG1vZCApICUgbW9kOwp9CgppbmxpbmUgaW50IGNob29zZU9kZChpbnQgbikKewoJcmV0dXJuIGZbbi0xXTsKfQoKaW5saW5lIGludCBnZXRNYXNrKGludCBudW0pCnsKCWludCBtYXNrID0gMDsKCglwID0gbnVtOwoKCS8vY291dCA8PCAibnVtPSIgPDwgbnVtIDw8IGVuZGw7CgoJd2hpbGUoIHAgPiAxICkKCXsKCQkvL2NvdXQgPDwgInByaW1lcz0iIDw8IHByaW1lc1twXSA8PCBlbmRsOwoJCW1hc2sgXj0gKCAxIDw8IGNvbnZbIHByaW1lc1twXSBdICk7CgoJCXAgLz0gcHJpbWVzW3BdOwoJfQoKCXJldHVybiBtYXNrOwp9Cgp2b2lkIHNvbHZlKCkKewoJaW5pdCgpOwoKCWIgPSAxMiAqIDc7CgoJLy9jb3V0IDw8ICJtYXNrPSIgPDwgZ2V0TWFzayhiKSA8PCBlbmRsOwoKCWludCBsaW0gPSAxIDw8IDIxOwoKCS8vIGhhbmRsZSAxcyBzZXBhcmF0ZWx5CgoJZm9ycihudW0sMSw3MSkKCXsKCQlpZiggYVtudW1dID4gMCApCgkJewoJCQlpZiggc3F1YXJlWyBudW0gXSA9PSB0cnVlICkKCQkJCWRwW2FjdF1bMF0gPSAoIGZbIGFbbnVtXSBdIC0gMSArIG1vZCApICUgbW9kOwoJCQllbHNlCgkJCXsKCQkJCWRwW2FjdF1bMF0gPSBjaG9vc2VFdmVuKCBhW251bV0gKTsKCgkJCQlpbnQgbWFzayA9IGdldE1hc2sobnVtKTsKCgkJCQlkcFthY3RdW21hc2tdID0gY2hvb3NlT2RkKCBhW251bV0gKTsKCQkJfQoJCQkKCQkJcCA9IG51bTsKCQkJYnJlYWs7CgkJfQoJfQoJCglmb3JyKG51bSxwKzEsNzEpCgl7CgkJaWYoIGFbbnVtXSA9PSAwICkgY29udGludWU7CgoJCWFjdCA9IDEgLSAoIHBhcyA9IGFjdCApOwoKCQltZW1zZXQoZHBbYWN0XSwwLHNpemVvZihkcFthY3RdKSk7CgoJCWludCBtYXNrUHJpbWUgPSBnZXRNYXNrKG51bSk7CgoJCWZvcnIobWFzaywwLGxpbSkKCQl7CgkJCWRwW2FjdF1bbWFza10gKz0gZHBbcGFzXVttYXNrUHJpbWVdOwoJCQlkcFthY3RdW21hc2tdICU9IG1vZDsKCgkJCWlmKCBtYXNrUHJpbWUgPT0gMCApCgkJCXsKCQkJCWRwW2FjdF1bbWFza10gKz0gMWxsICogZHBbcGFzXVttYXNrXSAqICggZlsgYVtudW1dIF0gLSAxICsgbW9kICkgJSBtb2Q7CgkJCQlkcFthY3RdW21hc2tdICU9IG1vZDsKCQkJCWRwW2FjdF1bbWFza10gKz0gKCBmWyBhW251bV0gXSAtIDEgKyBtb2QgKSAlIG1vZDsKCQkJCWRwW2FjdF1bbWFza10gJT0gbW9kOwoJCQkJY29udGludWU7CgkJCX0KCgkJCWRwW2FjdF1bbWFzayBeIG1hc2tQcmltZV0gKz0gMWxsICogZHBbcGFzXVttYXNrXSAqIGNob29zZU9kZChhW251bV0pICUgbW9kOwoJCQlkcFthY3RdW21hc2sgXiBtYXNrUHJpbWVdICU9IG1vZDsKCgkJCWRwW2FjdF1bbWFza10gKz0gMWxsICogZHBbcGFzXVttYXNrXSAqICggMSArIGNob29zZUV2ZW4oYVtudW1dKSApICUgbW9kOwoJCQlkcFthY3RdW21hc2tdICU9IG1vZDsKCQkJZHBbYWN0XVttYXNrXSArPSBjaG9vc2VFdmVuKGFbbnVtXSk7CgkJCWRwW2FjdF1bbWFza10gJT0gbW9kOwoJCX0KCX0KfQp2b2lkIG91dHB1dCgpCnsKCWNvdXQgPDwgZHBbYWN0XVswXTsKfQovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLyBteSBmdW5jdGlvbnMgLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCmludCBtYWluKCkgCnsKCWlucHV0KCk7Cglzb2x2ZSgpOwoJb3V0cHV0KCk7CglyZXR1cm4gMDsKfQovLy8vIE1BSU4gLy8vLyBNQUlOIC8vLy8gTUFJTiAvLy8vIE1BSU4gLy8vLyBNQUlOIC8vLy8gTUFJTiAvLy8vIE1BSU4gLy8vLw==