nEVSPn - Online C++ Compiler & Debugging Tool

/*
* Author: Geeza
*/

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define pb push_back
#define fin(a, n) for(int i = a; i < n; i++)
#define fjn(a, n) for(int j = a; j < n; j++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

using namespace std;

const double PI = acos(-1);
const int N = 1e5+5;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007, inf = 1e6;

string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
char dc[] = {'D', 'L', 'R', 'U'};

ll n;
vector<ll> v;
vector<int> idx, frequency;
int dp[71][1<<19];
vector<pair<int, int>> freq[71];
ll spf[72];

void precompute() {
    for (int i = 0; i < 72; i++) spf[i] = i;
    for (ll i = 2; i < 72; i++) {
        if (spf[i] == i) {
            for (ll j = i*i; j < 72; j+=i) spf[j] = i;
        }
    }
}

ll mul(ll a, ll b) {
    return (a%mod * b%mod)%mod;
}

ll calc(ll val, ll mask) {
    if (val == 71) return mask == 0;

    int &ret = dp[val][mask];
    if (~ret)return ret;
    ret = 0;
    ll ch1 = 0;
    ll ch2 = 0;
    if (frequency[val] > 0) {
        ll c = 1; // 2^(n-1)
        for (int i = 0; i+1 < frequency[val]; i++) {
            c *= 2;
            if (c >= mod) c -= mod;
        }
        ll newMask = 0;
        for (auto [x, f] : freq[val]) {
            if (f&1)newMask ^= (1ll<<idx[x]);
        }
        c %= mod;
        ch1 = calc(val+1, mask)%mod;
        ch2 = calc(val+1, mask^newMask)%mod;
        ret = (mul(c, ch1) + mul(c, ch2))%mod;
    }
    else ret = calc(val+1, mask)%mod;

    return ret;
}

void solve() {
    cin >> n;
    v.assign(n, 0);
    idx.assign(70, 0);
    frequency.assign(71, 0);
    vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};
    fin(0, n) cin >> v[i], frequency[v[i]]++;
    for (int i = 0, id = 0; i < primes.size(); i++) {
        idx[primes[i]] = id++;
    }

    for (int i = 2; i < 71; i++) {
        ll tmp = i;
        vector<int> f(70, 0);
        while (tmp > 1) {
            ll p = spf[tmp];
            tmp /= p;
            f[p]++;
        }

        for (int j = 2; j < 70; j++) {
            if (f[j] > 0) {
                freq[i].push_back({j, f[j]});
            }
        }
    }

    memset(dp, -1, sizeof(dp));

    cout << calc(1, 0)-1  << "\n";
}

int main() {
    FAST;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    precompute();
    int tt = 1; //cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}