#include<bits/stdc++.h>
using namespace std;
int n;
int vis[10000005];
bitset<5005>b[505],c[5005];
int a[505];
int tot=0;
void prew(int id,int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			int f=0;
			while(x%i==0){
				f^=1;
				x/=i;
			}
			if(f){
				if(!vis[i])vis[i]=++tot;
				b[id][vis[i]]=1;
			}
		}
	}
	if(x>1){
		if(!vis[x])vis[x]=++tot;
		b[id][vis[x]]=1;
	}
}
bool check(bitset<5005>tmp){
	for(int i=1;i<=tot;i++)if(tmp[i]==1){
		if(c[i][i]==0)return false;
		tmp^=c[i];
	}
	return true;
}
void ins(bitset<5005>tmp){
	for(int i=1;i<=tot;i++)if(tmp[i]==1){
		if(c[i][i]==0){
			c[i]=tmp;
			return;
		}
		tmp^=c[i];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)prew(i,a[i]);
	int ans=1;
	for(int i=1;i<=n;i++)if(!check(b[i])){
		ins(b[i]);
		ans=ans*2%1000000007;
	}
	printf("%d",ans);
	return 0;
}