#include <bits/stdc++.h>
using namespace std;
int n, a[505], cnt, ccnt;
bitset<4005>b[505];
unordered_map<int, int> ma;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		for (int j = 2; j * j <= a[i]; j++) {
			while (a[i] % (j * j) == 0) {
				a[i] /= j * j;
			}
		}
		if (a[i] == 1) {
			a[i] = 0;
		}
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j * j < a[i]; j++) {
			if (a[i] % j == 0) {
				a[i] /= j;
				if (ma.find(j) == ma.end()) {
					ma[j] = ++ccnt;
				}
				b[i][ma[j]] = 1;
			}
		}
		if (a[i]) {
			if (ma.find(a[i]) == ma.end()) {
				ma[a[i]] = ++ccnt;
			}
			b[i][ma[a[i]]] = 1;
		}
	}
	int lst = 0, maxn = -1;
	for (int i = 1; i <= ccnt && lst < n; i++) {
		maxn = 0;
		for (int j = lst + 1; j <= n; j++) {
			if (b[j][i]) {
				maxn = j;
			}
		}
		if (maxn == 0) continue;
		swap(b[lst + 1], b[maxn]);
		lst++;
		for (int j = lst + 1; j <= n; j++) {
			if (b[j][i]) {
				b[j] = b[j] ^ b[lst];
			}
		}
	}
	long long ans = 1;
	for (int i = 1; i <= lst; i++) {
		ans = ans * 2;
		ans %= 1000000007;
	}
	cout << ans;
}