Shared code

// add me on genshin impact! 607984574
// Problem: Square Subsets
// Attempted: 2025-07-29 14:20:22 EST

#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 0
#else
#include "/Users/envyaims/Documents/template/debug.cpp"
#endif
using namespace std;
using ll = long long;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define pq priority_queue
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORE(i,a,b) for(int i = (a); i <= (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)
#define sz(x) (int)x.size()
#define make_unique(v) v.erase(unique(all(v)), v.end());
 
template<class T> using minpq = pq<T, vector<T>, greater<T>>;
template<class T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
template<int D, typename T>struct vt : public vector<vt<D - 1, T>> { template<typename... Args>
	vt(int n = 0, Args... args) : vector<vt<D - 1, T>>(n, vt<D - 1, T>(args...)) {}};
template<typename T> struct vt<1, T> : public vector<T> {
	vt(int n = 0, const T& val = T()) : vector<T>(n, val) {}};
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

const int MOD = 1e9+7;

// returns a vector of length n, smallest prime that it can be divided by
// runs in O(nloglogn) time.
vector<int> primesieve(int n) {
    vector<int> sieve(n);
    iota(sieve.begin(), sieve.end(), 0);
    for (int i = 2; i < n; i++)
        if (sieve[i] == i)
            for (int j = 2*i; j < n; j += i)
                sieve[j] = min(sieve[j], i);
    return sieve;
}
 
// returns a sorted list of all primes less than or equal to n.
// runs in O(nloglogn) time.
vector<ll> primesupto(int n) {
    vector<int> sieve = primesieve(n+1);
    vector<ll> out;
    for (int i = 2; i <= n; i++)
        if (sieve[i] == i) out.push_back(i);
    return out;
}

// https://cp-algorithms.com/linear_algebra/rank-matrix.html

int compute_rank(vector<vector<int>> A) {
    int n = A.size();
    int m = A[0].size();

    int rank = 0;
    vector<bool> row_selected(n, false);
    for (int i = 0; i < m; ++i) {
        int j;
        for (j = 0; j < n; ++j) {
            if (!row_selected[j] && abs(A[j][i]) > 0)
                break;
        }

        if (j != n) {
            ++rank;
            row_selected[j] = true;
            for (int p = i + 1; p < m; ++p)
                A[j][p] /= A[j][i];
            for (int k = 0; k < n; ++k) {
                if (k != j && abs(A[k][i]) > 0) {
                    for (int p = i + 1; p < m; ++p)
                        A[k][p] -= A[j][p] * A[k][i];
                }
            }
        }
    }
    return rank;
}

void uwu(){
	int n; cin >> n;
	vector<int> a(n); cin >> a;
	auto primes = primesupto(5000);
	int m = sz(primes);
	vector<vector<int>> equations(n, vector<int>(m));
	FOR(i,0,n){
		FOR(j,0,m){
			while(a[i] % primes[j] == 0){
				equations[i][j] ^= 1;
				a[i] /= primes[j];
			}
		}
	}
	int rank = compute_rank(equations);
	int nullity = n - rank;
	ll ans = 1;
	FOR(i,0,nullity) ans = (ans * 2) % MOD;
	cout << ans << "\n";
}

signed main(){
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	// cin>>t;
	while(t--){
		uwu();
	}
}