# Untitled

unknown
plain_text
a month ago
1.8 kB
2
Indexable
Never
```#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <cassert>
#include <iomanip>
#include <cstring>
#include <stack>
#include <bitset>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N = 170;
const long long mod = 1e9 + 7;

int basis[170] = {}, sz = 0;
vector<bitset<N>>v(1001);

bitset<170> cur = v[n];
for (int i = 0; i < 170; ++i){
if (cur[i] == 0)
continue;
if (basis[i] == 0){
basis[i] = cur[i];
++sz;
return ;
}
cur ^= basis[i];
}
}

void solve(){
int n; cin >> n;
int total = 0;
int freq[1001] = {};
for (int i = 0 ; i < n; ++i){
int x; cin >> x;
freq[x] = 1;
}
vector<bool>isprime(1001, true);
int num = 0;
for (int i = 2; i <= 1000; ++i){
if (isprime[i]){
for (int j = i; j <= 1000; j += i){
int cur = j;
while(cur % i == 0){
cur /= i;
v[j][num] = 1 - v[j][num];
}
if (i != j) isprime[j] = false;
}
++num;
}
}
for (int i = 2; i <= 1000; ++i)
if (freq[i])
long long cur = n - sz;
long long ans = 1;
for (int i = 1; i <= cur; ++i)
ans = (2 * ans) % mod;
ans = (ans - 1) % mod;
ans = (ans + mod) % mod;
cout << ans;
}

int main(){
fast;
int t = 1; //cin >> t;
for (int i = 1; i <= t; ++i){
solve();
if (i != t)
cout << '\n';
}
}```